RAIROMercas-et-al-Binary-patterns-2014.pdf (666.17 kB)
0/0

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

Download (666.17 kB)
journal contribution
posted on 31.03.2017 by Robert Mercas, Pascal Ochem, Alexey V. Samsonov, Arseny M. Shur
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.

History

School

  • Science

Department

  • Computer Science

Published in

RAIRO - Theoretical Informatics and Applications

Volume

48

Issue

4

Pages

369 - 389

Citation

MERCAS, R. ... et al, 2014. Binary patterns in binary cube-free words: avoidability and growth. RAIRO - Theoretical Informatics and Applications, 48 (4), pp.369-389

Publisher

EDP Sciences

Version

VoR (Version of Record)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Publication date

2014

Notes

The original publication is available at www.rairo-ita.org.

ISSN

0988-3754

eISSN

1290-385X

Language

en

Exports

Logo branding

Keyword(s)

Exports