Unavoidable sets of constant length

Jean-Marc Champarnaud (1) , Georges Hansel (1) , Dominique Perrin (2)

1 LIFAR - Laboratoire d'informatique fondamentale et appliquée de Rouen
2 LIGM - Laboratoire d'Informatique Gaspard-Monge

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.

Domaines: Algorithme et structure de données [cs.DS]

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