Critical exponent of a word

In mathematics and computer science, the critical exponent of a finite or infinite sequence of symbols over a finite alphabet describes the largest number of times a contiguous subsequence can be repeated. For example, the critical exponent of "Mississippi" is 7/3, as it contains the string "ississi", which is of length 7 and period 3.

If w is an infinite word over the alphabet A and x is a finite word over A, then x is said to occur in w with exponent α, for positive real α, if there is a factor y of w with y = x^ax₀ where x₀ is a prefix of x, a is the integer part of α, and the length |y| = α |x|: we say that y is an α-power. The word w is α-power-free if it contains no factors which are β-powers for any β ≥ α.{{harvtxt|Krieger|2006}} p.281

The critical exponent for w is the supremum of the α for which w has α-powers,Berstel et al (2009) p.126 or equivalently the infimum of the α for which w is α-power-free.

Definition

If $\mathbf{w}$ is a word (possibly infinite), then the critical exponent of $\mathbf{w}$ is defined to be

: $E(\mathbf{w}) = \sup \{ r \in \mathbb{Q}^{\geq 1} : \mathbf{w} \, \text{ contains an } \, r \text{-power}\}$

where $\mathbb{Q}^{\geq 1} = \{ q \in \mathbb{Q} : q \geq 1 \}$ .{{Harvard citation text|Krieger|2006}} p.282

Examples

The critical exponent of the Fibonacci word is (5 + {{radic|5}})/2 ≈ 3.618.{{harvtxt|Allouche|Shallit|2003}} p. 37
The critical exponent of the Thue–Morse sequence is 2. The word contains arbitrarily long squares, but in any factor xxb the letter b is not a prefix of x.

Properties

The critical exponent can take any real value greater than 1.{{sfnp|Krieger|Shallit|2007}}
The critical exponent of a morphic word over a finite alphabet is either infinite or an algebraic number of degree at most the size of the alphabet.{{harvtxt|Krieger|2006}} p.280

Repetition threshold

The repetition threshold of an alphabet A of n letters is the minimum critical exponent of infinite words over A: clearly this value RT(n) depends only on n. For n=2, any binary word of length four has a factor of exponent 2, and since the critical exponent of the Thue–Morse sequence is 2, the repetition threshold for binary alphabets is RT(2) = 2. It is known that RT(3) = 7/4, RT(4) = 7/5 and that for n≥5 we have RT(n) ≥ n/(n-1). It is conjectured that the latter is the true value, and this has been established for 5 ≤ n ≤ 14 and for n ≥ 33.

Notes

References

{{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = Cambridge University Press | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
{{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=American Mathematical Society | year=2009 | isbn=978-0-8218-4480-9 | url=https://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }}
{{cite book | title=Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006 | volume=4036 | series=Lecture Notes in Computer Science | editor1-first=Oscar H. | editor1-last=Ibarra | editor2-first=Zhe | editor2-last=Dang | publisher=Springer-Verlag | year=2006 | isbn=3-540-35428-X | first=Dalia | last=Krieger | chapter=On critical exponents in fixed points of non-erasing morphisms | pages=280–291 | zbl=1227.68074 }}
{{cite journal | first1=D. | last1=Krieger | first2=J. | last2=Shallit | title=Every real number greater than one is a critical exponent | journal=Theor. Comput. Sci. | volume=381 | year=2007 | issue=1–3 | pages=177–182 | doi=10.1016/j.tcs.2007.04.037 | doi-access=free }}
{{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
{{cite book | last=Pytheas Fogg | first=N. | editor1=Berthé, Valérie|editor1-link=Valérie Berthé|editor2=Ferenczi, Sébastien|editor3=Mauduit, Christian|editor4=Siegel, A. | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | location=Berlin | publisher=Springer-Verlag | year=2002 | isbn=3-540-44141-7 | zbl=1014.11015 }}

Category:Formal languages

Category:Combinatorics on words