Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102422
Title: Binary patterns in binary cube-free words: Avoidability and growth
Authors: Mercaş, R.
Ochem, P.
Samsonov, A. V.
Shur, A. M.
Issue Date: 2014
Publisher: EDP Sciences
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 .
Keywords: AVOIDABILITY
AVOIDABLE PATTERN
CUBE-FREE WORD
FORMAL LANGUAGES
GROWTH RATE
MORPHISM
OVERLAP-FREE WORD
GROWTH RATE
AVOIDABILITY
AVOIDABLE PATTERNS
CUBE-FREE WORD
MORPHISMS
OVERLAP-FREE WORDS
FORMAL LANGUAGES
URI: http://hdl.handle.net/10995/102422
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84908460613
PURE ID: 401895
d88d8fd4-6b49-44fa-b654-a8804d5307c0
ISSN: 9883754
DOI: 10.1051/ita/2014015
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84908460613.pdf228,6 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.