Palabra sin cuadrados

En combinatoria , una palabra sin cuadrados es una palabra (una secuencia de símbolos) que no contiene ningún cuadrado. Un cuadrado es una palabra de la forma XX , donde X no está vacío. Por tanto, una palabra sin cuadrados también se puede definir como una palabra que evita el patrón XX .

Palabras finitas sin cuadrados

Alfabeto binario

En un alfabeto binario , las únicas palabras sin cuadrados son la palabra vacía y . ${\displaystyle \{0,1\}}$ ${\displaystyle \epsilon ,0,1,01,10,010}$ ${\displaystyle 101}$

Alfabeto ternario

Sobre un alfabeto ternario , hay infinitas palabras sin cuadrados. Es posible contar el número de palabras ternarias sin cuadrados de longitud n . ${\displaystyle \{0,1,2\}}$ ${\displaystyle c(n)}$

Este número está limitado por , donde . ^[2] El límite superior se puede encontrar mediante el lema de Fekete y la aproximación mediante autómatas . El límite inferior se puede encontrar encontrando una sustitución que preserve la libertad de cuadrados. ^[2] ${\displaystyle c(n)=\Theta (\alpha ^{n})}$ ${\textstyle 1.3017597<\alpha <1.3017619}$ ${\displaystyle \alpha }$

Alfabeto con más de tres letras.

Dado que hay infinitas palabras sin cuadrados en alfabetos de tres letras, esto implica que también hay infinitas palabras sin cuadrados en un alfabeto con más de tres letras.

La siguiente tabla muestra la tasa de crecimiento exacta de las palabras k -arias sin cuadrados, redondeadas a 7 dígitos después del punto decimal, para k en el rango de 4 a 15: ^[2]

palabras bidimensionales

Considere un mapa desde hasta A , donde A es un alfabeto y se llama palabra bidimensional. Sea la entrada . Una palabra es una línea de si existe tal que y para . ^[3] ${\displaystyle {\textbf {w}}}$ ${\displaystyle \mathbb {N} ^{2}}$ ${\displaystyle {\textbf {w}}}$ ${\displaystyle w_{m,n}}$ ${\displaystyle {\textbf {w}}(m,n)}$ ${\displaystyle {\textbf {x}}}$ ${\displaystyle {\textbf {w}}}$ ${\displaystyle i_{1},i_{2},j_{1},j_{2}}$ ${\displaystyle {\text{gcd}}(j_{1},j_{2})=1}$ ${\displaystyle t\geq 0,x_{t}=w_{{i_{1}}+{j_{1}t},{i_{2}}+{j_{2}t}}}$

Carpi ^[4] demuestra que existe una palabra bidimensional en un alfabeto de 16 letras, de modo que cada línea no tiene cuadrados. Una búsqueda por computadora muestra que no hay palabras bidimensionales en un alfabeto de 7 letras, de modo que cada línea no tiene cuadrados. ${\displaystyle {\textbf {w}}}$ ${\displaystyle {\textbf {w}}}$ ${\displaystyle {\textbf {w}}}$ ${\displaystyle {\textbf {w}}}$

Generando palabras finitas sin cuadrados

Shur ^[5] propone un algoritmo llamado R2F (random-t(w)o-free) que puede generar una palabra sin cuadrados de longitud n sobre cualquier alfabeto con tres o más letras. Este algoritmo se basa en una modificación de la compresión de entropía : selecciona aleatoriamente letras de un alfabeto de k letras para generar una palabra sin cuadrados. ${\displaystyle (k+1)}$

Se ingresa  el algoritmo R2F : tamaño del alfabeto , longitud de la palabra , salida: una palabra aria sin cuadrados w de longitud n . ${\displaystyle k\geq 2}$ ${\displaystyle n>1}$  ${\displaystyle (k+1)}$ (Tenga en cuenta que es el alfabeto con letras ). ${\textstyle \color {gray}\Sigma _{k+1}}$ ${\displaystyle \color {gray}\{1,...,k+1\}}$ (Para una palabra , es la permutación de tal que a precede a b en si la ${\displaystyle \color {gray}w\in \Sigma _{k}}$ ${\displaystyle \color {gray}\chi _{w}}$ ${\displaystyle \color {gray}\Sigma _{k}}$ ${\displaystyle \color {gray}\chi _{w}}$ La posición más a la derecha de a en w está a la derecha de la posición más a la derecha de b en w . Por ejemplo, tiene .) ${\displaystyle \color {gray}w=136263163\in \Sigma _{6}}$ ${\displaystyle \color {gray}\chi _{w}=361245}$ elija de manera uniforme y aleatoria conjunto seguido de todas las demás letras de en orden creciente establezca el número N de iteraciones en 0 ${\displaystyle w[1]}$ ${\textstyle \Sigma _{k+1}}$  ${\displaystyle \chi _{w}}$   ${\displaystyle w[1]}$ ${\textstyle \Sigma _{k+1}}$ mientras  elige j uniformemente al azar ${\displaystyle |w|<n}$  ${\textstyle \Sigma _{k}}$ agregar al final de w actualizar desplazando los primeros j elementos a la derecha y establecer el incremento N en 1 si w termina con un cuadrado de rango r, luego eliminar las últimas r letras de w ${\displaystyle a=\chi _{w}[j+1]}$ ${\displaystyle \chi _{w}}$ ${\displaystyle \chi _{w}[1]=a}$    volver ​

Cada palabra (k+1)-aria sin cuadrados puede ser el resultado del algoritmo R2F, porque en cada iteración puede agregar cualquier letra excepto la última letra de w .

El número esperado de letras k-arias aleatorias utilizadas por el algoritmo R2F para construir una palabra libre de cuadrados -arios de longitud n es ${\displaystyle (k+1)}$

$${\displaystyle N=n\left(1+{\frac {2}{k^{2}}}+{\frac {1}{k^{3}}}+{\frac {4}{k^{4}}}+O\left({\frac {1}{k^{5}}}\right)\right)+O(1).}$$

n^[6][7][8]n ${\displaystyle O(n\log n)}$ ${\displaystyle O(n^{2})}$

Infinitas palabras sin cuadrados

En cualquier alfabeto de tres o más letras existen palabras infinitamente largas y sin cuadrados , como lo demuestra Axel Thue . ^[9]

Ejemplos

Primera diferencia de la secuencia Thue-Morse

Un ejemplo de una palabra infinita sin cuadrados sobre un alfabeto de tamaño 3 es la palabra sobre el alfabeto obtenida tomando la primera diferencia de la secuencia Thue-Morse . ^[9] Es decir, de la secuencia Thue-Morse ${\displaystyle \{-1,0,+1\}}$

${\displaystyle 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0...}$

se forma una nueva secuencia en la que cada término es la diferencia de dos términos consecutivos de la secuencia Thue-Morse. La palabra libre de cuadrados resultante es

${\displaystyle 1,0,-1,1,-1,0,1,0,-1,0,1,-1,1,0,-1,...}$(secuencia A029883 en la OEIS ).

Morfismo de sanguijuela

Otro ejemplo encontrado por John Leech ^[10] se define recursivamente sobre el alfabeto . Sea cualquier palabra sin cuadrados que comience con la letra ${\displaystyle \{0,1,2\}}$ ${\displaystyle w_{1}}$0 . Defina las palabras de forma recursiva de la siguiente manera: la palabra se obtiene reemplazando cada una ${\displaystyle \{w_{i}\mid i\in \mathbb {N} \}}$ ${\displaystyle w_{i+1}}$ ${\displaystyle w_{i}}$0 dentro con ${\displaystyle w_{i}}$0121021201210 , cada uno1 con1202102012021 , y cada uno2 con2010210120102 . Es posible demostrar que la secuencia converge a la palabra infinita sin cuadrados.

0121021201210120210201202120102101201021202102012021...

Generando infinitas palabras sin cuadrados

Se pueden generar infinitas palabras sin cuadrados mediante morfismo sin cuadrados . Un morfismo se llama libre de cuadrados si la imagen de cada palabra libre de cuadrados está libre de cuadrados. Un morfismo se llama k – libre de cuadrados si la imagen de cada palabra libre de cuadrados de longitud k está libre de cuadrados.

Crochemore ^[11] demuestra que un morfismo uniforme h no tiene cuadrados si y sólo si no tiene 3 cuadrados. En otras palabras, h es libre de cuadrados si y solo si es libre de cuadrados para todo w libre de cuadrados de longitud 3. Es posible encontrar un morfismo libre de cuadrados mediante búsqueda de fuerza bruta . ${\displaystyle h(w)}$

Se genera  el algoritmo square-free_morphism : un morfismo sin cuadrados con el rango más bajo posible k . set  while True establezca k_sf_words en la lista de todas las palabras libres de cuadrados de longitud k sobre un alfabeto ternario para cada una en k_sf_words do para cada una en k_sf_words do para cada una en k_sf_words do if luego salga del bucle actual (avanzar al siguiente ) if y luego si es libre de cuadrados para todo w libre de cuadrados de longitud ${\displaystyle k=3}$      ${\displaystyle h(0)}$      ${\displaystyle h(1)}$      ${\displaystyle h(2)}$      ${\displaystyle h(1)=h(2)}$   ${\displaystyle h(1)}$  ${\displaystyle h(0)\neq h(1)}$   ${\displaystyle h(2)\neq h(0)}$    ${\displaystyle h(w)}$ 3  luego  devuelve el incremento k por ${\displaystyle h(0),h(1),h(2)}$1

En un alfabeto ternario, hay exactamente 144 morfismos uniformes sin cuadrados de rango 11 y ningún morfismo uniforme sin cuadrados con un rango inferior a 11.

Para obtener infinitas palabras sin cuadrados, comience con cualquier palabra sin cuadrados, como0 , y aplicarle sucesivamente un morfismo h libre de cuadrados . Las palabras resultantes conservan la propiedad de libertad de cuadrados. Por ejemplo, sea h un morfismo sin cuadrados, entonces como , es una palabra infinita sin cuadrados. ${\displaystyle w\to \infty }$ ${\displaystyle h^{w}(0)}$

Tenga en cuenta que, si un morfismo sobre un alfabeto ternario no es uniforme, entonces este morfismo no tiene cuadrados si y solo si no tiene 5 cuadrados. ^[11]

Combinaciones de letras en palabras sin cuadrados.

Ampliar una palabra sin cuadrados para evitar ab .

Evite combinaciones de dos letras

En un alfabeto ternario, una palabra sin cuadrados de longitud superior a 13 contiene todas las combinaciones de dos letras sin cuadrados. ^[12]

Esto se puede demostrar construyendo una palabra sin cuadrados sin la combinación de dos letras ab . Como resultado, bcba cbca cbaca es la palabra libre de cuadrados más larga sin la combinación ab y su longitud es igual a 13.

Tenga en cuenta que en un alfabeto de más de tres letras hay palabras sin cuadrados de cualquier longitud sin una combinación arbitraria de dos letras.

Evite combinaciones de tres letras

En un alfabeto ternario, una palabra sin cuadrados de longitud superior a 36 contiene todas las combinaciones de tres letras sin cuadrados. ^[12]

Sin embargo, hay palabras sin cuadrados de cualquier longitud sin la combinación de tres letras aba .

Tenga en cuenta que en un alfabeto de más de tres letras hay palabras sin cuadrados de cualquier longitud sin una combinación arbitraria de tres letras.

densidad de una letra

La densidad de una letra a en una palabra finita w se define como donde es el número de apariciones de a en y es la longitud de la palabra. La densidad de una letra a en una palabra infinita es donde está el prefijo de la palabra w de longitud l . ^[13] ${\displaystyle {\frac {|w|_{a}}{|w|}}}$ ${\displaystyle |w|_{a}}$ ${\displaystyle w}$ ${\displaystyle |w|}$ ${\displaystyle \liminf _{l\to \infty }{\frac {|w_{l}|_{a}}{|w_{l}|}}}$ ${\displaystyle w_{l}}$

La densidad mínima de una letra a en una palabra ternaria infinita sin cuadrados es igual a . ^[13] ${\displaystyle {\frac {883}{3215}}\approx 0.2747}$

La densidad máxima de una letra a en una palabra infinita ternaria sin cuadrados es igual a . ^[14] ${\displaystyle {\frac {255}{653}}\approx 0.3905}$

Notas

1. "A006156 - OEIS". oeis.org . Consultado el 28 de marzo de 2019 .
2. Shur, Arseny (2011). "Propiedades de crecimiento de los lenguajes libres de poder". Revisión de informática . 6 (5–6): 28–43. doi :10.1016/j.cosrev.2012.09.001.
3. Berthe, Valeria; Rigo, Michel, eds. (2016), "Prefacio", Combinatoria, palabras y dinámica simbólica , Cambridge University Press, págs. xi-xviii, doi :10.1017/cbo9781139924733.001, ISBN 9781139924733
4. Carpi, Arturo (1988). "Configuraciones multidimensionales no repetitivas". Informática Teórica . 56 (2): 233–241. doi : 10.1016/0304-3975(88)90080-1 . ISSN  0304-3975.
5. Shur, Arseny (2015). "Generar palabras sin cuadrados de manera eficiente". Informática Teórica . 601 : 67–72. doi : 10.1016/j.tcs.2015.07.027 . hdl : 10995/92700 .
6. Apostólico, A.; Preparata, FP (febrero de 1983). "Detección óptima fuera de línea de repeticiones en una cadena". Informática Teórica . 22 (3): 297–315. doi : 10.1016/0304-3975(83)90109-3 . ISSN  0304-3975.
7. Crochemore, Max (octubre de 1981). "Un algoritmo óptimo para calcular las repeticiones de una palabra". Cartas de procesamiento de información . 12 (5): 244–250. doi :10.1016/0020-0190(81)90024-7. ISSN  0020-0190.
8. Principal, Michael G; Lorentz, Richard J (septiembre de 1984). "Un algoritmo O (n log n) para encontrar todas las repeticiones en una cadena". Revista de algoritmos . 5 (3): 422–432. doi :10.1016/0196-6774(84)90021-x. ISSN  0196-6774.
9. Berstel, Jean (1994). "Los artículos de Axel Thue sobre repeticiones en palabras y una traducción" . Departamentos de Matemáticas e Informática, Universidad de Québec en Montreal. ISBN 978-2892761405. OCLC  494791187.
10. Sanguijuela, J. (1957). "Un problema en hilos de cuentas". Matemáticas. Gaz . 41 : 277–278. doi :10.1017/S0025557200236115. S2CID  126406225. Zbl  0079.01101.
11. Berstel, Jean (abril de 1984). "Algunos resultados recientes sobre Squarefree Words". Simposio Anual sobre Aspectos Teóricos de la Informática . Apuntes de conferencias sobre informática. 166 : 14-25. doi :10.1007/3-540-12920-0_2. ISBN 978-3-540-12920-2.
12. Zolotov, Boris (2015). "Otra solución al problema de las palabras que no se repiten". arXiv : 1505.00019 [matemáticas.CO].
13. Khalyavin, Andrey (2007). "La densidad mínima de una letra en una palabra ternaria infinita sin cuadrados es 883/3215" (PDF) . Diario de secuencias enteras . 10 (2): 3. Código Bib : 2007JIntS..10...65K.
14. Ochem, Pascal (2007). "Frecuencia de letras en infinitas palabras sin repeticiones". Informática Teórica . 380 (3): 388–392. doi :10.1016/j.tcs.2007.03.027. ISSN  0304-3975.

Referencias

• Berstel, Jean ; Lauve, Aarón; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Palabras de Christoffel y repeticiones en palabras. Serie de monografías de CRM. vol. 27. Providence, RI: Sociedad Matemática Estadounidense . ISBN 978-0-8218-4480-9. Zbl  1161.68043.
• Lotario, M. (1997). Combinatoria sobre palabras . Cambridge: Prensa de la Universidad de Cambridge . ISBN 978-0-521-59924-5..
• Lotario, M. (2011). Combinatoria algebraica sobre palabras . Enciclopedia de Matemáticas y sus aplicaciones. vol. 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, 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 978-3-540-44141-0. Zbl  1014.11015.