Binary patterns in binary cube-free words: avoidability and growth
From MaRDI portal
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.
Recommendations
Cited in
(10)- Polynomial versus exponential growth in repetition-free binary words
- Growth rate of binary words avoiding \(xxx^{R}\)
- Avoiding cross-bifix-free binary words
- On the aperiodic avoidability of binary patterns with variables and reversals
- Growth properties of power-free languages
- Properties of a class of Toeplitz words
- Binary words avoiding xx^Rx and strongly unimodal sequences
- On the tree of binary cube-free words
- Avoiding letter patterns in ternary square-free words
- Constructing premaximal binary cube-free words of any level
This page was built for publication: Binary patterns in binary cube-free words: avoidability and growth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934274)
