Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/51421
Title: ON PANSIOT WORDS AVOIDING 3-REPETITIONS
Authors: Gorbunova, Irina A.
Shur, Arseny M.
Issue Date: 2012
Citation: Gorbunova I. A. ON PANSIOT WORDS AVOIDING 3-REPETITIONS / Irina A. Gorbunova, Arseny M. Shur // International Journal of Foundations of Computer Science. — 2012. — Vol. 23. — № 8. — P. 1583-1594.
Abstract: The recently confirmed Dejean's conjecture about the threshold between avoidable and unavoidable powers of words gave rise to interesting and challenging problems on the structure and growth of threshold words. Over any finite alphabet with k ≥ 5 letters, Pansiot words avoiding 3-repetitions form a regular language, which is a rather small superset of the set of all threshold words. Using cylindric and 2-dimensional words, we prove that, as k approaches infinity, the growth rates of complexity for these regular languages tend to the growth rate of complexity of some ternary 2-dimensional language. The numerical estimate of this growth rate is ≈1.2421. © 2012 World Scientific Publishing Company.
Keywords: 2-DIMENSIONAL WORDS
COMBINATORIAL COMPLEXITY
CYLINDRIC WORDS
DEJEAN'S CONJECTURE
PANSIOT WORDS
THRESHOLD LANGUAGES
URI: http://hdl.handle.net/10995/51421
https://elar.urfu.ru/handle/10995/51421
SCOPUS ID: 84875286715
WOS ID: 000316500200002
PURE ID: 1066202
ISSN: 0129-0541
1793-6373
DOI: 10.1142/S0129054112400631
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
1108.3630.pdf173,82 kBAdobe PDFView/Open


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