Binary patterns in binary cube-free words: Avoidability and growth

Abstract : 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.
Type de document :
Article dans une revue
RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2014, 48 (4), pp.369-389. 〈10.1051/ita/2014015〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01263848
Contributeur : Pascal Ochem <>
Soumis le : jeudi 28 janvier 2016 - 12:22:35
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

Robert Mercaş, Pascal Ochem, Alexey V. Samsonov, Arseny M. Shur. Binary patterns in binary cube-free words: Avoidability and growth. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2014, 48 (4), pp.369-389. 〈10.1051/ita/2014015〉. 〈lirmm-01263848〉

Partager

Métriques

Consultations de la notice

48