Inventories of unavoidable languages and the word-extension conjecture

摘要

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). (C) 1998 Published by Elsevier Science B.V. All rights reserved. [References: 21]