Skip to Main content Skip to Navigation
Journal articles

Unavoidable sets of constant length

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Dominique Perrin Connect in order to contact the contributor
Submitted on : Sunday, February 24, 2013 - 1:05:01 AM
Last modification on : Saturday, January 15, 2022 - 3:57:59 AM
Long-term archiving on: : Saturday, May 25, 2013 - 2:35:08 AM


Files produced by the author(s)



Jean-Marc Champarnaud, Georges Hansel, Dominique Perrin. Unavoidable sets of constant length. International Journal of Algebra and Computation, World Scientific Publishing, 2004, 14 (1), pp.241-251. ⟨10.1142/S0218196704001700⟩. ⟨hal-00619542⟩



Record views


Files downloads