Exponente crítico de una palabra

En matemáticas e informática , el exponente crítico de una secuencia finita o infinita de símbolos sobre un alfabeto finito describe el mayor número de veces que se puede repetir una subsecuencia contigua . Por ejemplo, el exponente crítico de "Mississippi" es 7/3, ya que contiene la cadena "ississi", que tiene una longitud de 7 y un periodo de 3.

Si w es una palabra infinita sobre el alfabeto A y x es una palabra finita sobre A , entonces se dice que x aparece en w con exponente α, para un α real positivo, si existe un factor y de w tal que y = x ^a x ₀ donde x ₀ es un prefijo de x , a es la parte entera de α, y la longitud | y | = α | x |: decimos que y es una potencia de α . La palabra w está libre de potencias de α si no contiene factores que sean potencias de β para ningún β ≥ α. ^{[ 1 ]}

El exponente crítico para w es el supremo de los α para los cuales w tiene potencias de α, ^{[ 2 ]} o equivalentemente el ínfimo de los α para los cuales w no tiene potencias de α. ^{[ 3 ]}

Si${\displaystyle \mathbf {w} }$es una palabra (posiblemente infinita), entonces el exponente crítico de${\displaystyle \mathbf {w} }$se define como

${\displaystyle E(\mathbf {w} )=\sup\{r\in \mathbb {Q} ^{\geq 1}:\mathbf {w} \,{\text{ contiene una }}\,r{\text{-potencia}}\}}$

dónde${\displaystyle \mathbb {Q} ^{\geq 1}=\{q\in \mathbb {Q} :q\geq 1\}}$. ^{[ 4 ]}

• El exponente crítico de la palabra de Fibonacci es (5  + √ 5 )/2 ≈ 3,618. ^{[ 3 ] [ 5 ]} 
• El exponente crítico de la secuencia de Thue-Morse es 2. ^{[ 3 ]} La palabra contiene cuadrados arbitrariamente largos, pero en cualquier factor xxb la letra b no es un prefijo de x .

• El exponente crítico puede tomar cualquier valor real mayor que 1. ^{[ 3 ] [ 6 ]}
• El exponente crítico de una palabra morfológica sobre un alfabeto finito es infinito o un número algebraico de grado como máximo igual al tamaño del alfabeto. ^{[ 3 ]}

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 RT(n) = n/(n-1) for n ≥ 5. ^[2][5]

• Critical exponent of a physical system

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
• Krieger, Dalia (2006). "On critical exponents in fixed points of non-erasing morphisms". In Ibarra, Oscar H.; Dang, Zhe (eds.). Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006. Lecture Notes in Computer Science. Vol. 4036. Springer-Verlag. pp. 280–291. ISBN 3-540-35428-X. Zbl 1227.68074.
• Krieger, D.; Shallit, J. (2007). "Every real number greater than one is a critical exponent". Theor. Comput. Sci. 381 (1–3): 177–182. doi:10.1016/j.tcs.2007.04.037.
• Lothaire, M. (2011). Combinatoria algebraica en palabras . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  90. Con prólogo de Jean Berstel y Dominique Perrin (Reimpresión de la  edición en tapa dura de 2002). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183 . 
• Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, cristiano; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de conferencias de matemáticas. vol.  1794. Berlín: Springer-Verlag . ISBN 3-540-44141-7. Zbl 1014.11015 .