On pansiot words avoiding 3-repetitions
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
On pansiot words avoiding 3-repetitions
|
|
| Автор |
Gorbunova, I. A.
Shur, A. M. |
|
| Тематика |
COMPUTATIONAL METHODS
COMPUTER SCIENCE FINITE ALPHABET CONTEXT FREE LANGUAGES |
|
| Описание |
The recently confirmed Dejean?fs 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 forma regular language, which is a rather small superset of the set of all thresholdwords. Using cylindric and 2-dimensionalwords, 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. © 2011 I. A. Gorbunova, A. M. Shur.
|
|
| Дата |
2024-04-24T12:38:23Z
2024-04-24T12:38:23Z 2011 |
|
| Тип |
Article
Journal article (info:eu-repo/semantics/article) Published version (info:eu-repo/semantics/publishedVersion) |
|
| Идентификатор |
Gorbunova, I. A., & Shur, A. M. (2011). On pansiot words avoiding 3-repetitions. Electronic Proceedings in Theoretical Computer Science, 63, 138–146. doi:10.4204/eptcs.63.19
2075-2180 Final All Open Access, Gold, Green https://arxiv.org/pdf/1108.3630 http://elar.urfu.ru/handle/10995/132577 10.4204/EPTCS.63.19 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
cc-by-nc-nd |
|
| Формат |
application/pdf
|
|
| Издатель |
Open Publishing Association
|
|
| Источник |
Electronic Proceedings in Theoretical Computer Science
Electronic Proceedings in Theoretical Computer Science, EPTCS |
|