zbMATH — the first resource for mathematics

Inventories of unavoidable languages and the word-extension conjecture. (English) Zbl 0902.68099
Summary: 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 says 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).

68Q45 Formal languages and automata
03D40 Word problems, etc. in computability and recursion theory
Full Text: DOI
[1] Aho, A.V.; Corasick, M.J., Efficient string machines, an aid to bibliographic research, Comm. ACM, 18, 6, 333-340, (1975) · Zbl 0301.68048
[2] Bean, D.R.; Ehrenfeucht, A.; McNulty, G.F., Avoidable patterns in strings of symbols, Pacific J. math, 85, 2, 261-294, (1979) · Zbl 0428.05001
[3] Bucher, W.; Ehrenfeucht, A.; Haussler, D., On total regulators generated by derivation relations, (), 71-79 · Zbl 0571.68056
[4] Choffrut, C.; Culik, K., On extendibility of unavoidable sets, Discrete appl. math., 9, 125-137, (1984) · Zbl 0629.68080
[5] Crochemore, M.; Lerest, M.; Wender, P., An optimal test on finite unavoidable sets of words, Inform. process. lett., 16, 179-180, (1983) · Zbl 0506.68057
[6] Dickson, L.E., Finiteness of the odd perfect and primitive abundant numbers with r distinct prime factors, Am. J. math., 35, 413-422, (1903) · JFM 44.0220.02
[7] Ehrenfeucht, A.; Haussler, D.; Rozenberg, G., On regularity of context-free languages, Theoret. comput. sci., 27, 311-332, (1983) · Zbl 0553.68044
[8] Fine, N.J.; Wilf, H.S., Uniqueness theorem for periodic functions, (), 109-114 · Zbl 0131.30203
[9] Higman, G., Ordering by divisibility in abstract algebras, (), 326-336 · Zbl 0047.03402
[10] Kruskal, Well-quasi ordering, the tree theorem, and Vazsonyi’s conjecture, Trans. amer. math. soc., 95, 210-225, (1960) · Zbl 0158.27002
[11] Kruskal, The theory of well-quasi ordering: a frequently discovered concept, J. combin. theory ser. A, 13, 3, 297-305, (1972) · Zbl 0244.06002
[12] Kucherov, G.; Rusinovitch, M., On ground-reducibility problem for word rewriting systems with variables, ()
[13] G. Kucherov, M. Rusinovitch, Complexity of testing ground reducibility for linear word rewriting systems with variables, preprint.
[14] Lallement, G., Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025
[15] Perrin, D., (), Chap. 1.
[16] Sakarovitch, J., ()
[17] Ochmanski, E., Inevitability in concurrent systems, Inform. process. lett., 25, 221-225, (1987) · Zbl 0653.68011
[18] Puel, L., Using unavoidable sets of trees to generalize Kruskal’s theorem, J. symbolic computation, 8, 4, 335-382, (1989) · Zbl 0676.06003
[19] Rosaz, L., Unavoidable languages, cuts and innocent sets of words, Theoret. inform. appl. (RAIRO), 29, 5, 339-382, (1995) · Zbl 0838.68068
[20] Rosaz, L., Unavoidable languages, Mémoire de thèse, (1993) · Zbl 0838.68068
[21] Schutzenberger, M.P., On the synchronizing properties of certain prefix codes, Inform. and control, 7, 23-36, (1964) · Zbl 0122.15004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.