Please use this identifier to cite or link to this item:
|Title:||Binary patterns in binary cube-free words: Avoidability and growth|
Samsonov, A. V.
Shur, A. M.
|Citation:||Binary patterns in binary cube-free words: Avoidability and growth / R. Mercaş, P. Ochem, A. V. Samsonov, et al. — DOI 10.1051/ita/2014015 // RAIRO - Theoretical Informatics and Applications. — 2014. — Vol. 48. — Iss. 4. — P. 369-389.|
|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. © 2014 EDP Sciences .|
|Appears in Collections:||Научные публикации, проиндексированные в SCOPUS и WoS CC|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.