On Pansiot Words Avoiding 3-Repetitions

Abstract

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.