Binary patterns in binary cube-free words: Avoidability and growth - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue RAIRO - Theoretical Informatics and Applications (RAIRO: ITA) Année : 2014

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

Résumé

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.

Dates et versions

lirmm-01263848 , version 1 (28-01-2016)

Identifiants

Citer

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), 2014, 48 (4), pp.369-389. ⟨10.1051/ita/2014015⟩. ⟨lirmm-01263848⟩
86 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More