Namespaces
Variants
Actions

Difference between revisions of "Critical exponent of a word"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Critical exponent of a word)
 
m (→‎References: isbn link)
 
(One intermediate revision by one other user not shown)
Line 16: Line 16:
  
 
====Repetition threshold====
 
====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 \ge 5$ we have $RT(n) \ge 1 + 1/(n-1)$.  It is conjectured that the latter is the true value, and this has been established for $5 \le n \le 14$ and for $n \ge 33$.
+
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 \ge 5$ we have $RT(n) = 1 + 1/(n-1)$.
  
  
 
====References====
 
====References====
* Allouche, Jean-Paul; Shallit, Jeffrey; "Automatic Sequences: Theory, Applications, Generalizations", Cambridge University Press (2003) ISBN 978-0-521-82332-6 {{ZBL|1086.11015}}
+
* Allouche, Jean-Paul; Shallit, Jeffrey; "Automatic Sequences: Theory, Applications, Generalizations", Cambridge University Press (2003) {{ISBN|978-0-521-82332-6}} {{ZBL|1086.11015}}
* Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; "Combinatorics on words. Christoffel words and repetitions in words", CRM Monograph Series '''27''' American Mathematical Society (2009) ISBN 978-0-8218-4480-9 {{ZBL|1161.68043}}
+
* Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; "Combinatorics on words. Christoffel words and repetitions in words", CRM Monograph Series '''27''' American Mathematical Society (2009) {{ISBN|978-0-8218-4480-9}} {{ZBL|1161.68043}}
* Krieger, Dalia; ''On critical exponents in fixed points of non-erasing morphisms'' pp. 280–291 in Oscar H. Ibarra, Zhe Dang (edd.) "Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006", Lecture Notes in Computer Science '''4036''' , Springer (2006) ISBN 3-540-35428-X {{ZBL|1227.68074}}
+
* Currie, James; Rampersad, Narad; "A proof of Dejean's conjecture" ''Math. Comp.'' '''80''' (2011), 1063-1070. {{DOI|10.1090/S0025-5718-2010-02407-X}}. {{MR|2772111}}  {{ZBL|1215.68192}}
 +
* Krieger, Dalia; ''On critical exponents in fixed points of non-erasing morphisms'' pp. 280–291 in Oscar H. Ibarra, Zhe Dang (edd.) "Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006", Lecture Notes in Computer Science '''4036''' , Springer (2006) {{ISBN|3-540-35428-X}} {{ZBL|1227.68074}}
 
* Krieger, D.; Shallit, J.; ''Every real number greater than one is a critical exponent'', Theor. Comput. Sci., '''381''' (2007), pp. 177–182 {{DOI|10.1016/j.tcs.2007.04.037}}
 
* Krieger, D.; Shallit, J.; ''Every real number greater than one is a critical exponent'', Theor. Comput. Sci., '''381''' (2007), pp. 177–182 {{DOI|10.1016/j.tcs.2007.04.037}}
* Lothaire, M.; "Algebraic combinatorics on words", Encyclopedia of Mathematics and Its Applications '''90''' Cambridge University Press,  (2011)  ISBN 978-0-521-18071-9 {{ZBL|1221.68183}}
+
* Lothaire, M.; "Algebraic combinatorics on words", Encyclopedia of Mathematics and Its Applications '''90''' Cambridge University Press,  (2011)  {{ISBN|978-0-521-18071-9}} {{ZBL|1221.68183}}
* Pytheas Fogg, N.; "Substitutions in dynamics, arithmetics and combinatorics", Lecture Notes in Mathematics '''1794''' Springer (2002)  ISBN 3-540-44141-7 {{ZBL|1014.11015}}
+
* Pytheas Fogg, N.; "Substitutions in dynamics, arithmetics and combinatorics", Lecture Notes in Mathematics '''1794''' Springer (2002)  {{ISBN|3-540-44141-7}} {{ZBL|1014.11015}}
 +
* Rao, Michaël; "Last cases of Dejean’s conjecture". ''Theor. Comput. Sci.'' '''412''' (2011) 3010-3018.  {{DOI|10.1016/j.tcs.2010.06.020}}. {{ZBL|1230.68163}}

Latest revision as of 20:21, 7 November 2023

2020 Mathematics Subject Classification: Primary: 68R15 [MSN][ZBL]

For a finite or infinite word 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 finite alphabet $A$ and $x$ is a finite word over $A$, then $x$ is said to occur in $w$ with exponent $\alpha$, for positive real $\alpha$, if there is a factor $y$ of $w$ with $y = x^a x_p$ where $x_p$ is a prefix of $x$, $a$ is the integer part of $\alpha$, and the length $|y| \ge \alpha |x|$|: we say that $y$ is an $\alpha$-power. The word $w$ is $\alpha$-power-free if it contains no factors which are $\alpha$-powers.

The critical exponent for $w$ is the supremum of the $\alpha$ for which $w$ has $\alpha$-powers, or equivalently the infimum of the $\alpha$ for which $w$ is $\alpha$-power-free.

Examples

  • The critical exponent of the Fibonacci word is $\frac{5+\sqrt5}{2} = 3.618\ldots$.
  • 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 an algebraic number of degree at most the size of the alphabet.

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 \ge 5$ we have $RT(n) = 1 + 1/(n-1)$.


References

  • Allouche, Jean-Paul; Shallit, Jeffrey; "Automatic Sequences: Theory, Applications, Generalizations", Cambridge University Press (2003) ISBN 978-0-521-82332-6 Zbl 1086.11015
  • Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; "Combinatorics on words. Christoffel words and repetitions in words", CRM Monograph Series 27 American Mathematical Society (2009) ISBN 978-0-8218-4480-9 Zbl 1161.68043
  • Currie, James; Rampersad, Narad; "A proof of Dejean's conjecture" Math. Comp. 80 (2011), 1063-1070. DOI 10.1090/S0025-5718-2010-02407-X. MR2772111 Zbl 1215.68192
  • Krieger, Dalia; On critical exponents in fixed points of non-erasing morphisms pp. 280–291 in Oscar H. Ibarra, Zhe Dang (edd.) "Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006", Lecture Notes in Computer Science 4036 , Springer (2006) ISBN 3-540-35428-X Zbl 1227.68074
  • Krieger, D.; Shallit, J.; Every real number greater than one is a critical exponent, Theor. Comput. Sci., 381 (2007), pp. 177–182 DOI 10.1016/j.tcs.2007.04.037
  • Lothaire, M.; "Algebraic combinatorics on words", Encyclopedia of Mathematics and Its Applications 90 Cambridge University Press, (2011) ISBN 978-0-521-18071-9 Zbl 1221.68183
  • Pytheas Fogg, N.; "Substitutions in dynamics, arithmetics and combinatorics", Lecture Notes in Mathematics 1794 Springer (2002) ISBN 3-540-44141-7 Zbl 1014.11015
  • Rao, Michaël; "Last cases of Dejean’s conjecture". Theor. Comput. Sci. 412 (2011) 3010-3018. DOI 10.1016/j.tcs.2010.06.020. Zbl 1230.68163
How to Cite This Entry:
Critical exponent of a word. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Critical_exponent_of_a_word&oldid=39646