Inventories of unavoidable languages and the word-extension conjecture

Autor:	Laurent Rosaz
Rok vydání:	1998
Předmět:	Philosophy of language Combinatorics Monoid Conjecture Cardinality Finite-state machine General Computer Science Extension (predicate logic) Word (group theory) Counterexample Mathematics Theoretical Computer Science Computer Science(all)
Zdroj:	Theoretical Computer Science. 201(1-2):151-170
ISSN:	0304-3975
DOI:	10.1016/s0304-3975(97)00031-5
Popis:	A language X on an alphabet A is unavoidable iff all but finitely many words in A ∗ have a factor in X. In this paper, I prove that the inventory of unavoidable languages of n words can be explicitly made for every n, that the reduced unavoidable languages of given cardinality are finite in number (an unavoidable language is minimal if no proper subset is unavoidable, it is reduced if it is minimal and if whenever a word is replaced by a proper factor, the resulting unavoidable language is not minimal), and I give a counterexample to the word-extension conjecture (which said that in every unavoidable language, there is a word w and a letter a, such that the language, where w is replaced by wa, is still unavoidable).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f206c352d35b64b7bcfcd0e0acf0a45d Zobrazit plný text záznamu Full Text from ScienceDirect