Palabra recurrente

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

Una palabra uniformemente recurrente es una palabra recurrente en el que para cualquier factor dado X en la secuencia, hay una cierta longitud n _X (a menudo mucho más larga 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).

Ejemplos de

• La manera más fácil de hacer una secuencia recurrente es para formar una secuencia periódica , uno donde la secuencia se repite por completo después de un número dado m de pasos. Secuencia de una de este tipo es entonces uniformemente recurrente y n _X se puede ajustar a cualquier múltiplo de m que es mayor que dos veces la longitud de X . Una secuencia recurrente que en última instancia es 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 sturmianas son uniformemente recurrentes. ^[10]

Referencias

1. Lothaire (2011) p. 30
2. Allouche y Shallit (2003) p.325
3. Pytheas Fogg (2002) p.2
4. Lothaire (2011) p. 141
5. Berstel et al (2009) p.133
6. Berthé y Rigo (2010) p.7
7. Allouche y Shallit (2003) p.328
8. Pytheas Fogg (2002) p.6
9. Lothaire (2011) p.31
10. Berthé y Rigo (2010) p.177

• 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 .
• Berthé, Valérie ; Rigo, Michel, eds. (2010). Combinatoria, autómatas y teoría de números . Enciclopedia de Matemáticas y sus Aplicaciones. 135 . Cambridge: Cambridge University Press . ISBN 978-0-521-51597-9. Zbl  1197.68006 .
• 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, Anne (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 .
• Un. Muchnik, A. Semenov, M. Ushakov, Secuencias casi periódicas, Theoret. Computación. Sci. vol.304 no.1-3 (2003), 1-33.

Este artículo relacionado con el álgebra es un fragmento . Puedes ayudar a Wikipedia expandiéndolo .

• v
• t
• mi