Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/51421
Название: | ON PANSIOT WORDS AVOIDING 3-REPETITIONS |
Авторы: | Gorbunova, Irina A. Shur, Arseny M. |
Дата публикации: | 2012 |
Библиографическое описание: | 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. |
Аннотация: | 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. |
Ключевые слова: | 2-DIMENSIONAL WORDS COMBINATORIAL COMPLEXITY CYLINDRIC WORDS DEJEAN'S CONJECTURE PANSIOT WORDS THRESHOLD LANGUAGES |
URI: | http://elar.urfu.ru/handle/10995/51421 |
Идентификатор SCOPUS: | 84875286715 |
Идентификатор WOS: | 000316500200002 |
Идентификатор PURE: | 1066202 |
ISSN: | 0129-0541 1793-6373 |
DOI: | 10.1142/S0129054112400631 |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
1108.3630.pdf | 173,82 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.