En combinatoria, una palabra libre de cuadrados (también denominada palabra sin cuadrados) es una cadena de caracteres (una sucesión de símbolos) que no contiene cuadrados, es decir, no contiene grupos de la forma , donde no es un valor vacío. Por lo tanto, una palabra sin cuadrados también puede definirse como una palabra que carece del patrón .

Palabras finitas sin cuadrados

Alfabeto binario Sobre un alfabeto binario , las únicas palabras sin cuadrados son la palabra vacía y y .

Alfabeto ternario Sobre un alfabeto ternario , existen infinitas palabras sin cuadrados. Es posible contar el número de palabras ternarias libres de cuadrados de longitud .

+Número de palabras ternarias de longitud n libres de cuadrados0123456789101112136121830426078108144204264 Este número está acotado por , donde . La cota superior de se puede hallar mediante el lema de Fekete y la aproximación mediante teoría de autómatas. La cota inferior se puede hallar encontrando una sustitución que preserve la ausencia de cuadrados.

Alfabeto con más de tres letras Dado que existen infinitas palabras libres de cuadrados sobre alfabetos de tres letras, esto implica que también existen infinitas palabras libres de cuadrados sobre un alfabeto con más de tres letras.

La siguiente tabla muestra la tasa de crecimiento exacta de las palabras -arias libres de cuadrados, redondeada a 7 decimales, para en el rango de 4 a 15:

+Tasa de crecimiento de las palabras libres de cuadrados -ariasTamaño de alfabeto ()456789Tasa de crecimiento2.62150803.73253864.79140695.82846616.85411737.8729902Tamaño del alfabeto ()101112131415Tasa de crecimiento8.88748569.898981310.908327911.916080412.922616713.9282035

Palabras bidimensionales Considérese una función de a , donde es un alfabeto y se denomina una palabra bidimensional. Sea la entrada . Una palabra es una línea de si existe tal que , y para .

Carpi demostró que existe una palabra bidimensional sobre un alfabeto de 16 letras tal que cada línea de está libre de cuadrados. Una búsqueda computacional muestra que no existen palabras bidimensionales sobre un alfabeto de 7 letras tales que cada línea de esté libre de cuadrados.

Generación de palabras finitas libres de cuadrados Shur propuso un algoritmo llamado R2F (random-t(w)o-free) que puede generar una palabra libre de cuadrados de longitud sobre cualquier alfabeto de 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 libre de cuadrados -aria.

Algoritmo R2F es entrada: tamaño del alfabeto , longitud de la palabra salida: una palabra libre de cuadrados -aria de longitud .

(Nótese que es el alfabeto con letras .) (Para una palabra , es la permutación de tal que precede a en si la posición más a la derecha de en está a la derecha de la posición más a la derecha de en . Por ejemplo, tiene .

Seleccionar de de forma aleatoria y uniforme. Establecer en , seguido de todas las demás letras de en orden ascendente. Establecer el número de iteraciones en 0. Mientras hacer: Seleccionar de de forma aleatoria y uniforme. Añadir al final de . Actualizar desplazando los primeros elementos de a la derecha y estableciendo . Incrementar en . Si termina con un cuadrado de Clasificar entonces Eliminar las últimas letras de devolver

Cada palabra libre de cuadrados (k+1)-aria puede ser la salida del Algoritmo R2F, ya que en cada iteración puede añadir cualquier letra excepto la última de .

El número esperado de letras k-arias aleatorias utilizadas por el Algoritmo R2F para construir una palabra libre de cuadrados -aria de longitud es: Cabe destacar que existe un algoritmo que puede verificar la ausencia de cuadrados de una palabra de longitud en tiempo . Apostólico y Preparata presentan un algoritmo que utiliza árboles de sufijos. Crochemore utiliza particionamiento en su algoritmo. Main y Lorentz proporcionan un algoritmo basado en el método de divide y vencerás. Una implementación ingenua puede requerir un tiempo de para verificar que una palabra de longitud no contenga cuadrados.

Palabras infinitas libres de cuadrados Existen palabras infinitas libres de cuadrados en cualquier alfabeto con tres o más letras, como lo demuestra Axel Thue.

Ejemplos

Primera diferencia de la sucesión de Thue-Morse Un ejemplo de una palabra infinita libre de cuadrados sobre un alfabeto de tamaño 3 es la palabra sobre el alfabeto obtenida al tomar la relación de recurrencia de la sucesión de Thue-Morse. Es decir, a partir de la sucesión de Thue-Morse:

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

.

Morfismo de Leech Otro ejemplo hallado por Leech se define recursivamente sobre el alfabeto . Sea cualquier palabra libre de cuadrados que comience con la letra . Se definen las palabras recursivamente de la siguiente manera: la palabra se obtiene de reemplazando cada en por , cada por y cada por . Es posible demostrar que la sucesión converge a la palabra infinita libre de cuadrados:

Generación de palabras libres de cuadrados infinitas Las palabras libres de cuadrados infinitas se pueden generar mediante morfismos libres de cuadrados. Un morfismo se denomina libre de cuadrados si la imagen de cada palabra libre de cuadrados es libre de cuadrados. Un morfismo se denomina k–libre de cuadrados si la imagen de cada palabra libre de cuadrados de longitud k es libre de cuadrados.

Crochemore demuestra que un morfismo uniforme es libre de cuadrados si y solo si es 3-libre de cuadrados. En otras palabras, es libre de cuadrados si y solo si es libre de cuadrados para todos los morfismos libres de cuadrados de longitud 3. Es posible encontrar un morfismo libre de cuadrados mediante búsqueda de fuerza bruta.

Algoritmo morfismo_libre_cuadrados es Salida: un morfismo libre_cuadrados con el rango más bajo posible . establecer mientras Verdadero hacer establecerk_sf_wordsa la lista de todas las palabras libres de cuadrados de longitud sobre un alfabeto ternario para cada en k_sf_words hacer para cada en k_sf_words hacer para cada en k_sf_words hacer si entonces salir del bucle actual (avanzar al siguiente ) si y entonces si es libre de cuadrados para todos los libres de cuadrados de longitud entonces devuelve Incrementa en una

Sobre un alfabeto ternario, existen exactamente 144 morfismos uniformes libres de cuadrados de rango 11 y ningún morfismo uniforme libre de cuadrados con un rango inferior a 11.

Para obtener una palabra infinita libre de cuadrados, se parte de cualquier palabra libre de cuadrados como y se le aplica sucesivamente un morfismo libre de cuadrados . Las palabras resultantes conservan la propiedad de ser libres de cuadrados. Por ejemplo, sea un morfismo libre de cuadrados; entonces, como , es una palabra infinita libre de cuadrados.

Cabe destacar que, si un morfismo sobre un alfabeto ternario no es uniforme, este morfismo es libre de cuadrados si y solo si es 5-libre de cuadrados.

Combinaciones de letras en palabras libres de cuadrados

Evitar combinaciones de dos letras Sobre un alfabeto ternario, una palabra libre de cuadrados de longitud mayor que 13 contiene todas las combinaciones de dos letras libres de cuadrados.

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

Cabe destacar que en un alfabeto de más de tres letras existen palabras sin cuadrados de cualquier longitud sin una combinación arbitraria de dos letras.

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

Cabe destacar que en un alfabeto de más de tres letras existen palabras sin cuadrados de cualquier longitud sin una combinación arbitraria de tres letras.

Densidad de la letra La densidad de la letra en una palabra finita se define como , donde es el número de ocurrencias de en y es la longitud de la palabra. La densidad de la letra en una palabra infinita es , donde es el prefijo de la palabra de longitud .

La densidad mínima de la letra en una palabra ternaria infinita libre de cuadrados es igual a .

La densidad máxima de la letra en una palabra ternaria infinita libre de cuadrados es igual a .

Referencias

Bibliografía

Categoría:Lenguajes formales Categoría:Combinatoria