| Author(s): |
JEAN-MARC CHAMPARNAUD
LIFAR, Université de Rouen,
B.P. 67, 76 130 Mont Saint Aignan, France
GEORGES HANSEL
LIFAR, Université de Rouen,
B.P. 67, 76 130 Mont Saint Aignan, France
DOMINIQUE PERRIN
Institut Gaspard Monge,
Université de Marne-la-Vallée,
77454 Marne-la-Vallée cedex 2, France
|
| 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. |
