Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-08-18
EPTCS 63, 2011, pp. 138-146
Computer Science
Formal Languages and Automata Theory
In Proceedings WORDS 2011, arXiv:1108.3412
Scientific paper
10.4204/EPTCS.63.19
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.
Gorbunova Irina A.
Shur Arseny M.
No associations
LandOfFree
On Pansiot Words Avoiding 3-Repetitions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Pansiot Words Avoiding 3-Repetitions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Pansiot Words Avoiding 3-Repetitions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-180616