Sesquipower

En matemáticas, una palabra sesquipower o Zimin es una cadena sobre un alfabeto con prefijo y sufijo idénticos . Los sesquipowers son patrones inevitables , en el sentido de que todas las cadenas suficientemente largas contienen uno.

Definicion formal

Formalmente, dejó un ser un alfabeto y A ^* sea el monoide libre de cadenas finitas más de  una . Cada palabra w no vacía en A ⁺ es un sesquipoder de orden 1. Si u es un sesquipower de orden n, entonces cualquier palabra w = uvu es un sesquipower de orden n  + 1. ^[1] El grado de una palabra no vacía w es el entero más grande d tal que w es un sesquipoder de orden d . ^[2]

Secuencia bi-ideal

Una secuencia bi-ideal es una secuencia de palabras f _i donde f ₁ está en A ⁺ y

${\displaystyle f_{i+1}=f_{i}g_{i}f_{i}\ }$

para algunos g _i en A ^∗ e i  ≥ 1. El grado de una palabra w es, por lo tanto, la longitud de la secuencia bi-ideal más larga que termina en w . ^[2]

Patrones inevitables

Para un alfabeto finito A en k cartas, no es un número entero M en función de k y n , tal que cualquier palabra de longitud M tiene un factor que es una sesquipower de orden al menos n . Expresamos esto diciendo que los sesquipopotencias son patrones inevitables . ^{[3] [4]}

Sesquipowers en infinitas secuencias

Dada una secuencia bi-ideal infinita, observamos que cada f _i es un prefijo de f _{i +1} y, por lo tanto, f _i converge en una secuencia infinita

${\displaystyle f=f_{1}g_{1}f_{1}g_{2}f_{1}g_{1}f_{1}g_{3}f_{1}\cdots \ }$

Definimos una palabra infinita como sesquipoder si es el límite de una secuencia bi-ideal infinita. ^[5] Una palabra infinita es un sesquipoder si y solo si es una palabra recurrente , ^{[5] [6]} es decir, cada factor ocurre con una frecuencia infinita. ^[7]

Arregle un alfabeto finito A y asuma un orden total en las letras. Para los números enteros p y n dados , toda palabra suficientemente larga en A ^∗ tiene un factor que es una potencia p o un factor que es una potencia n ; en este último caso el factor tiene un n - factorización en palabras Lyndon . ^[6]

Ver también

• Patrón ABACABA

Referencias

1. Lothaire (2011) p. 135
2. Lothaire (2011) p. 136
3. Lothaire (2011) p. 137
4. Berstel et al (2009) p.132
5. Lothiare (2011) p. 141
6. Berstel et al (2009) p.133
7. Lothaire (2011) p. 30

• 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 .
• 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 .