Binary Patterns in Binary Cube-Free Words: Avoidability and Growth

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

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-01
Main Authors: Mercas, Robert, Ochem, Pascal, Samsonov, Alexei V, Shur, Arseny M
Format: Article
Language:English
Subjects:
Languages
Polynomials
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1301.4682