Page 1

Displaying 1 – 4 of 4

Showing per page

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

Robert Mercaş, Pascal Ochem, Alexey V. Samsonov, Arseny M. Shur (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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...

Currently displaying 1 – 4 of 4

Page 1