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''^''a''''x''₀ 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 β ≥ α. 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$ is a word (possibly infinite), then the ''critical exponent'' of $\mathbf$ is defined to be
:$E(\mathbf) = \sup \$
where $\mathbb^ = \$. p.282

Examples

* The critical exponent of the Fibonacci word is (5 + )/2 ≈ 3.618. 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.
* 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. 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.

See also

* Critical exponent of a physical system

Notes

References

*
*
*
*
*
* {{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

Formal languages
Combinatorics on words