Paper Info
Title
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.
Year
DOI
Venue
2013
10.1051/ita/2014015
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Keywords
DocType
Volume
Formal languages,avoidability,avoidable pattern,cube-free word,overlap-free word,growth rate,morphism
Journal
48
Issue
ISSN
Citations 
SP4
0988-3754
3
PageRank 
References 
Authors
0.44
14
4
Name
Order
Citations
PageRank
Robert Mercas16912.83
Pascal Ochem225836.91
Alexey V. Samsonov350.82
Arseny M. Shur415226.47