Palabra recurrente

En matemáticas, una palabra o secuencia recurrente es una palabra infinita sobre un alfabeto finito en la que cada factor aparece infinitas veces. ^{[ 1 ] [ 2 ] [ 3 ]} Una palabra infinita es recurrente si y solo si es una sesquipotencia . ^{[ 4 ] [ 5 ]}

Una palabra recurrente uniforme es una palabra recurrente en la que para cualquier factor X dado en la secuencia, existe alguna longitud n _X (a menudo mucho mayor que la longitud de X ) tal que X aparece en cada bloque de longitud n _X. ^{[ 1} ] ^{[ 6 ] [ 7 ]} También se utilizan los términos secuencia mínima ^{[ 8 ]} y secuencia casi periódica (Muchnik, Semenov ^, Ushakov 2003).

• La forma más sencilla de crear una secuencia recurrente es formar una secuencia periódica , en la que la secuencia se repite completamente después de un número m de pasos. Dicha secuencia es uniformemente recurrente y nX puede ser cualquier múltiplo de m mayor que el doble de la longitud de X. Una secuencia recurrente que es, en última instancia _, periódica es puramente periódica. ^{[ 2 ]}
• La secuencia de Thue-Morse es uniformemente recurrente sin ser periódica, ni siquiera eventualmente periódica (es decir, periódica después de algún segmento inicial no periódico). ^{[ 9 ]}
• Todas las palabras de Sturm son uniformemente recurrentes. ^{[ 10 ]}

• 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). Combinatoria de palabras. Palabras de Christoffel y repeticiones en palabras . Serie de monografías CRM. Vol.  27. Providence, RI: American Mathematical Society . ISBN 978-0-8218-4480-9. Zbl 1161.68043 . 
• Berthé, Valérie ; Rigo, Michel, eds. (2010). Combinatoria, autómatas y teoría de números . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  135. Cambridge: Cambridge University Press . ISBN 978-0-521-51597-9. Zbl 1197.68006 . 
• 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, Anne (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 . 
• An. Muchnik, A. Semenov, M. Ushakov, Secuencias casi periódicas, Theoret. Comput. Sci. vol.304 no.1-3 (2003), 1-33.