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 es de longitud 7 y período 3.
Si w es una palabra infinito sobre el alfabeto A y x es una palabra finita sobre A , entonces x se dice que ocurrir en w con exponente α, para α real positivo, si hay un factor y de w con y = x un x 0 donde x 0 es un prefijo de x , a es la parte entera de α y la longitud | y | ≥ α | x |: decimos que y es una potencia α . La palabra w esLibre de potencia α si no contiene factores que sean potencias α. [1]
El exponente crítico para w es el superior de α para el que w tiene α-potencia, [2] o, de manera equivalente, el mínimo de α para el que w es α-potencia libre. [3]
Ejemplos de
- El exponente crítico de la palabra Fibonacci es (5 + √ 5 ) / 2 ≈ 3.618. [3] [4]
- El exponente crítico de la secuencia 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 .
Propiedades
- El exponente crítico puede tomar cualquier valor real mayor que 1. [3] [5]
- El exponente crítico de una palabra mórfica sobre un alfabeto finito es infinito o un número algebraico de grados como máximo del tamaño del alfabeto. [3]
Umbral de repetición
El umbral de repetición de un alfabeto A de n letras es el mínimo exponente crítico de infinitas palabras sobre A : claramente este valor RT ( n ) depende solo de n . Para n = 2, cualquier palabra binaria de longitud cuatro tiene un factor de exponente 2, y dado que el exponente crítico de la secuencia Thue-Morse es 2, el umbral de repetición para alfabetos binarios es RT (2) = 2. Se sabe que RT (3) = 7/4, RT (4) = 7/5 y que para n ≥5 tenemos RT ( n ) ≥ n / ( n -1). Se conjetura que este último es el valor verdadero, y esto se ha establecido para 5 ≤ n ≤ 14 y para n ≥ 33. [2] [4] Recientemente, M. Rao completó la demostración para todos los valores de n .
Ver también
- Exponente crítico de un sistema físico
Notas
- ^ Krieger (2006) p.281
- ↑ a b Berstel et al (2009) p.126
- ↑ a b c d e Krieger (2006) p.280
- ↑ a b Allouche y Shallit (2003) p. 37
- ^ Krieger y Shallit (2007) .
Referencias
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Prensa de la Universidad de Cambridge . ISBN 978-0-521-82332-6. Zbl 1086.11015 .
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Christoffel palabras y repeticiones en palabras . Serie de monografías CRM. 27 . Providence, RI: Sociedad Matemática Estadounidense . ISBN 978-0-8218-4480-9. Zbl 1161.68043 .
- Krieger, Dalia (2006). "Sobre exponentes críticos en puntos fijos de morfismos no borrables". En Ibarra, Oscar H .; Maldita sea, Zhe (eds.). Desarrollos en la teoría del lenguaje: Actas de la 10ª Conferencia Internacional, DLT 2006, Santa Bárbara, CA, EE. UU., 26 al 29 de junio de 2006 . Apuntes de conferencias en Ciencias de la Computación. 4036 . Springer-Verlag . págs. 280-291. ISBN 3-540-35428-X. Zbl 1227.68074 .
- Krieger, D .; Shallit, J. (2007). "Todo número real mayor que uno es un exponente crítico" . Theor. Computación. Sci . 381 : 177-182. doi : 10.1016 / j.tcs.2007.04.037 .
- Lothaire, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de las matemáticas y sus aplicaciones. 90 . Con prefacio de Jean Berstel y Dominique Perrin (Reimpresión de la edición de tapa dura de 2002). Prensa de la Universidad de Cambridge. ISBN 978-0-521-18071-9. Zbl 1221.68183 .
- Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de clase en matemáticas. 1794 . Berlín: Springer-Verlag . ISBN 3-540-44141-7. Zbl 1014.11015 .