Binary patterns in binary cube-free words: Avoidability and growth∗
Christian-Albrechts-Universität zu Kiel, Institut für Informatik,
2 CNRS, LIRMM, France.
3 Ural Federal University, Ekaterinburg, Russia. ;
Received: 14 March 2014
Accepted: 17 March 2014
The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted upper bounds. Finally, a new example of a pattern-avoiding language of polynomial growth is given.
Mathematics Subject Classification: 68Q70 / 68R15
Key words: Formal languages / avoidability / avoidable pattern / cube-free word / overlap-free word / growth rate / morphism
© EDP Sciences 2014