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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619542
Contributor : Dominique Perrin <>
Submitted on : Sunday, February 24, 2013 - 1:05:01 AM
Last modification on : Thursday, February 7, 2019 - 5:46:35 PM
Long-term archiving on: Saturday, May 25, 2013 - 2:35:08 AM

File

Unavoidable.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

217

Files downloads

446