文章基本信息

标题：On Pansiot Words Avoiding 3-Repetitions
本地全文：下载
作者：Irina A. Gorbunova ; Arseny M. Shur
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2011
卷号：63
页码：138-146
DOI：10.4204/EPTCS.63.19
出版社：Open Publishing Association
摘要：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 about 1.2421.