No Access

UNAVOIDABLE SETS OF CONSTANT LENGTH

JEAN-MARC CHAMPARNAUD

LIFAR, Université de Rouen, B.P. 67, 76 130 Mont Saint Aignan, France

Search for more papers by this author

GEORGES HANSEL

LIFAR, Université de Rouen, B.P. 67, 76 130 Mont Saint Aignan, France

Search for more papers by this author

, and

DOMINIQUE PERRIN

Institut Gaspard Monge, Université de Marne-la-Vallée, 77454 Marne-la-Vallée cedex 2, France

Search for more papers by this author

https://doi.org/10.1142/S0218196704001700Cited by:21 (Source: Crossref)

Abstract

A set of words X is called unavoidable on a given alphabet A if every infinite word on A has a factor in X. For k,q≥1, let c(k,q) be the number of conjugacy classes of words of length k on q letters. An unavoidable set of words of length k on q symbols has at least c(k,q) elements. We show that for any k,q≥1, there exists an unavoidable set of words of length k on q symbols having c(k,q) elements.

Keywords:

AMSC: 68R15

References

J.-M. Champarnaud and G. Hansel, Bull. Belg. Math. Soc. (2003). Google Scholar
J.-P. Duval, J. Algorithms 4(4), 363 (1983), DOI: 10.1016/0196-6774(83)90017-2. Crossref, Web of Science, Google Scholar
H. Fredricksen and J. Maiorana, Discrete Math. 23(3), 207 (1978), DOI: 10.1016/0012-365X(78)90002-X. Crossref, Web of Science, Google Scholar
M. R. Garey and D. S. Johnson , Computers and Intractability. A guide to the theory of NP-completeness , A Series of Books in the Mathematical Sciences ( W. H. Freeman and Co. , San Francisco, CA , 1979 ) . Google Scholar
G.-N. Han and D. Perrin, Sém. Lothar. Combin. 47, (2001). Google Scholar
D. E. Knuth , The Art of Computer Programming 4 ( Addison Wesley , 2002 ) , http://www-cs-faculty.stanford.edu/~knuth/news01.html . Google Scholar
D. Lind and B. H. Marcus , An Introduction to Symbolic Dynamics and Coding ( Cambridge , 1995 ) . Crossref, Google Scholar
M. Lothaire , Combinatorics on Words ( Cambridge University Press , Cambridge , 1997 ) . Crossref, Google Scholar
M. Lothaire , Algebraic Combinatorics on Words ( Cambridge University Press , 2002 ) . Crossref, Google Scholar
E. Moreno, A note on the theorem of Fredericksen and Maiorana, Adv. Appl. Math., to appear . Google Scholar
J. Mykkeltveit, J. Combin. Theory B 13, 40 (1972), DOI: 10.1016/0095-8956(72)90006-8. Crossref, Web of Science, Google Scholar
C. Reutenauer , Free Lie Algebras , Oxford Science Publications ( The Clarendon Press Oxford University Press , New York , 1993 ) . Crossref, Google Scholar
L. Rosaz, Theor. Comput. Sci. 201(1–2), 151 (1998), DOI: 10.1016/S0304-3975(97)00031-5. Crossref, Web of Science, Google Scholar
C. J. Saker and P. M. Higgins, Inf. Comput. 173(2), 222 (2002), DOI: 10.1006/inco.2001.3123. Crossref, Web of Science, Google Scholar
M.-P. Schützenberger, Inf. Contr. 7, 23 (1964), DOI: 10.1016/S0019-9958(64)90232-3. Crossref, Google Scholar
R. P. Stanley , Enumerative Combinatorics 1 ( Cambridge University Press , Cambridge , 1997 ) . Crossref, Google Scholar