BINARY PATTERNS IN BINARY CUBE-FREE WORDS: AVOIDABILITY AND GROWTH / Mercas Robert,Ochem Pascal,Samsonov Alexey V.,Shur Arseny M. // RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS. - 2014. - V. 48, l. 4, SI. - P. 369-389.

ISSN/EISSN:

0988-3754 / 1290-385X

Type:

Article

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.

Author keywords:

Formal languages; avoidability; avoidable pattern; cube-free word; overlap-free word; growth rate; morphism MORPHISMS; SEQUENCE; SYMBOLS

DOI:

10.1051/ita/2014015

Web of Science ID:

ISI:000344620500001

Соавторы в МНС:

Другие поля

Поле	Значение
Month	OCT
Publisher	EDP SCIENCES S A
Address	17, AVE DU HOGGAR, PA COURTABOEUF, BP 112, F-91944 LES ULIS CEDEX A, FRANCE
Language	English
EISSN	1290-385X
Keywords-Plus	MORPHISMS; SEQUENCE; SYMBOLS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Information Systems
Author-Email	rgm@informatik.uni-kiel.de Pascal.Ochem@lirmm.fr vonosmas@gmail.com Arseny.Shur@usu.ru
ResearcherID-Numbers	Mercas, Robert/L-5044-2016
ORCID-Numbers	Mercas, Robert/0000-0001-6034-433X
Funding-Acknowledgement	Alexander von Humboldt Foundation
Funding-Text	Robert Mercas was supported during his work by the Alexander von Humboldt Foundation while affiliated at Otto-von-Guericke-Universitat Magdeburg, Germany.
Number-of-Cited-References	25
Usage-Count-Last-180-days	2
Usage-Count-Since-2013	10
Journal-ISO	Rairo-Theor. Inform. Appl.
Doc-Delivery-Number	AT0IQ