ELibM mirror of EPTCS 63

On Pansiot Words Avoiding 3-Repetitions

Irina A. Gorbunova
(Ural Federal University)
Arseny M. Shur
(Ural Federal University)

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.

In Petr Ambrož, Štěpán Holub and Zuzana Masáková: Proceedings 8th International Conference Words 2011 (WORDS 2011), Prague, Czech Republic, 12-16th September 2011, Electronic Proceedings in Theoretical Computer Science 63, pp. 138–146.
Published: 17th August 2011.

ArXived at: http://dx.doi.org/10.4204/EPTCS.63.19 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org