La combinatoria de palabras es un campo relativamente nuevo de las matemáticas , que se deriva de la combinatoria , que se centra en el estudio de las palabras y los lenguajes formales . La materia estudia las letras o los símbolos y las secuencias que forman. La combinatoria de palabras afecta a varias áreas de estudio matemático, incluidas el álgebra y la informática . Ha habido una amplia gama de contribuciones al campo. Algunos de los primeros trabajos fueron sobre palabras sin cuadrados realizados por Axel Thue a principios del siglo XX. Él y sus colegas observaron patrones dentro de las palabras e intentaron explicarlos. A medida que pasó el tiempo, la combinatoria de palabras se volvió útil en el estudio de algoritmos y codificación . Condujo a desarrollos en álgebra abstracta y a responder preguntas abiertas.
La combinatoria es un área de las matemáticas discretas . Las matemáticas discretas son el estudio de las estructuras contables. Estos objetos tienen un principio y un final definidos. El estudio de los objetos enumerables es lo opuesto a disciplinas como el análisis , donde se estudian el cálculo y las estructuras infinitas . La combinatoria estudia cómo contar estos objetos utilizando varias representaciones. La combinatoria sobre palabras es un desarrollo reciente en este campo que se centra en el estudio de las palabras y los lenguajes formales. Un lenguaje formal es cualquier conjunto de símbolos y combinaciones de símbolos que las personas utilizan para comunicar información. [1]
Primero se debe explicar cierta terminología relevante para el estudio de las palabras. En primer lugar, una palabra es básicamente una secuencia de símbolos, o letras, en un conjunto finito . [1] Uno de estos conjuntos es conocido por el público en general como el alfabeto . Por ejemplo, la palabra "enciclopedia" es una secuencia de símbolos en el alfabeto inglés , un conjunto finito de veintiséis letras. Dado que una palabra puede describirse como una secuencia, se pueden aplicar otras descripciones matemáticas básicas. El alfabeto es un conjunto , por lo que, como se esperaría, el conjunto vacío es un subconjunto . En otras palabras, existe una palabra única de longitud cero. La longitud de la palabra está definida por el número de símbolos que componen la secuencia, y se denota por . [1] Volviendo a mirar el ejemplo "enciclopedia", , ya que enciclopedia tiene doce letras. La idea de factorizar números grandes se puede aplicar a las palabras, donde un factor de una palabra es un bloque de símbolos consecutivos. [1] Por lo tanto, "cyclop" es un factor de "enciclopedia".
Además de examinar las secuencias en sí mismas, otra área a considerar de la combinatoria sobre palabras es cómo se pueden representar visualmente. En matemáticas se utilizan varias estructuras para codificar datos. Una estructura común utilizada en combinatoria es la estructura de árbol . Una estructura de árbol es un gráfico donde los vértices están conectados por una línea, llamada camino o arista . Los árboles pueden no contener ciclos y pueden o no estar completos. Es posible codificar una palabra, ya que una palabra se construye mediante símbolos, y codificar los datos utilizando un árbol. [1] Esto da una representación visual del objeto.
Los primeros libros sobre combinatoria de palabras que resumen los orígenes de la materia fueron escritos por un grupo de matemáticos que colectivamente se hacían llamar M. Lothaire . Su primer libro se publicó en 1983, cuando la combinatoria de palabras se había vuelto más extendida. [1]
Un importante colaborador del desarrollo de la combinatoria en palabras fue Axel Thue (1863-1922); investigó la repetición. La principal contribución de Thue fue la prueba de la existencia de infinitas palabras sin cuadrados . Las palabras sin cuadrados no tienen factores repetidos adyacentes. [1] Para aclarar, "dining" no es libre de cuadrados ya que "in" se repite consecutivamente, mientras que "servers" es libre de cuadrados, sus dos factores "er" no son adyacentes. Thue demuestra su conjetura sobre la existencia de infinitas palabras sin cuadrados mediante el uso de sustituciones . Una sustitución es una forma de tomar un símbolo y reemplazarlo con una palabra. Utiliza esta técnica para describir su otra contribución, la secuencia Thue-Morse o palabra Thue-Morse. [1]
Thue escribió dos artículos sobre palabras sin cuadrados, el segundo de los cuales trataba sobre la palabra Thue-Morse. Marston Morse está incluido en el nombre porque descubrió el mismo resultado que Thue, pero trabajaron de forma independiente. Thue también demostró la existencia de una palabra sin superposición. Una palabra sin superposición es cuando, para dos símbolos y , el patrón no existe dentro de la palabra. En su segundo artículo, continúa demostrando una relación entre infinitas palabras sin superposición y palabras sin cuadrados. Toma palabras sin superposición que se crean utilizando dos letras diferentes y demuestra cómo se pueden transformar en palabras sin cuadrados de tres letras utilizando la sustitución. [1]
Como se describió anteriormente, las palabras se estudian examinando las secuencias formadas por los símbolos. Se encuentran patrones y se pueden describir matemáticamente. Los patrones pueden ser patrones evitables o inevitables. Un contribuyente significativo al trabajo de patrones inevitables o regularidades fue Frank Ramsey en 1930. Su importante teorema establece que para los números enteros , , existe un entero menos positivo tal que, a pesar de que un gráfico completo esté coloreado con dos colores, siempre existirá un subgráfico de color sólido de cada color. [1]
Entre otros autores que contribuyeron al estudio de los patrones inevitables se encuentra van der Waerden . Su teorema establece que si los números enteros positivos se dividen en clases, entonces existe una clase tal que contiene una progresión aritmética de longitud desconocida. Una progresión aritmética es una secuencia de números en la que la diferencia entre números adyacentes permanece constante. [1]
Al examinar patrones inevitables, también se estudian las sesquipotencias . Para algunos patrones , , , una sesquipotencia tiene la forma , , , . Este es otro patrón, como los patrones libres de cuadrados o inevitables. Coudrain y Schützenberger estudiaron principalmente estas sesquipotencias para aplicaciones de teoría de grupos . Además, Zimin demostró que todas las sesquipotencias son inevitables. Ya sea que aparezca el patrón completo o solo una parte de la sesquipotencia aparezca repetidamente, no es posible evitarlo. [1]
Los collares se construyen a partir de palabras de secuencias circulares. Se utilizan con mayor frecuencia en música y astronomía . Flye Sainte-Marie en 1894 demostró que existen collares binarios de De Bruijn de longitud . Un collar de De Bruijn contiene factores formados por palabras de longitud n sobre un cierto número de letras. Las palabras aparecen solo una vez en el collar. [1]
En 1874, Baudot desarrolló el código que eventualmente reemplazaría al código Morse al aplicar la teoría de los collares binarios de De Bruijn. El problema continuó de Sainte-Marie a Martin en 1934, quien comenzó a estudiar algoritmos para formar palabras con la estructura de De Bruijn. Luego, Klaas Posthumus trabajó en él en 1943. [1]
Posiblemente el resultado más aplicado en la combinatoria sobre palabras es la jerarquía de Chomsky , desarrollada por Noam Chomsky . Estudió el lenguaje formal en la década de 1950. [2] Su forma de ver el lenguaje simplificó el tema. Ignora el significado real de la palabra, no considera ciertos factores como la frecuencia y el contexto, y aplica patrones de términos cortos a todos los términos largos. La idea básica del trabajo de Chomsky es dividir el lenguaje en cuatro niveles, o la jerarquía del lenguaje . Los cuatro niveles son: regular , libre de contexto , sensible al contexto y computablemente enumerable o sin restricciones. [2] El regular es el menos complejo, mientras que el computablemente enumerable es el más complejo. Si bien su trabajo surgió de la combinatoria sobre palabras, afectó drásticamente a otras disciplinas, especialmente a la informática . [3]
Las palabras sturmianas , creadas por François Sturm, tienen sus raíces en la combinatoria de palabras. Existen varias definiciones equivalentes de palabras sturmianas. Por ejemplo, una palabra infinita es sturmiana si y solo si tiene factores distintos de longitud , para cada entero no negativo . [1]
Una palabra Lyndon es una palabra sobre un alfabeto dado que se escribe en su forma más simple y ordenada fuera de su respectiva clase de conjugación . Las palabras Lyndon son importantes porque para cualquier palabra Lyndon dada , existen palabras Lyndon y , con , . Además, existe un teorema de Chen, Fox y Lyndon que establece que cualquier palabra tiene una factorización única de palabras Lyndon, donde las palabras de factorización no son crecientes . Debido a esta propiedad, las palabras Lyndon se utilizan para estudiar álgebra , específicamente teoría de grupos . Forman la base para la idea de conmutadores . [1]
Cobham contribuyó con trabajos relacionados con el trabajo de Eugène Prouhet con autómatas finitos . Un grafo matemático está formado por aristas y nodos . Con autómatas finitos, las aristas se etiquetan con una letra del alfabeto. Para utilizar el grafo, uno comienza en un nodo y viaja a lo largo de las aristas hasta llegar a un nodo final. El camino tomado a lo largo del grafo forma la palabra. Es un grafo finito porque hay un número contable de nodos y aristas, y solo un camino conecta dos nodos distintos . [1]
Los códigos de Gauss , creados por Carl Friedrich Gauss en 1838, se desarrollan a partir de gráficos. En concreto, se necesita una curva cerrada en un plano . Si la curva solo se cruza sobre sí misma un número finito de veces, entonces se etiquetan las intersecciones con una letra del alfabeto utilizado. Al viajar a lo largo de la curva, la palabra se determina registrando cada letra a medida que se pasa por una intersección. Gauss se dio cuenta de que la distancia entre el momento en que aparece el mismo símbolo en una palabra es un número entero par . [1]
Walther Franz Anton von Dyck inició el trabajo de combinatoria sobre palabras en la teoría de grupos con su trabajo publicado en 1882 y 1883. Comenzó utilizando palabras como elementos de un grupo. Lagrange también contribuyó en 1771 con su trabajo sobre grupos de permutación . [1]
Un aspecto de la combinatoria de palabras que se estudia en la teoría de grupos son las palabras reducidas. Un grupo se construye con palabras de algún alfabeto que incluya generadores y elementos inversos , excluyendo los factores que aparecen en la forma aā o āa, para alguna a en el alfabeto. Las palabras reducidas se forman cuando los factores aā, āa se utilizan para cancelar elementos hasta que se alcanza una palabra única. [1]
También se desarrollaron transformaciones de Nielsen . Para un conjunto de elementos de un grupo libre , una transformación de Nielsen se logra mediante tres transformaciones: reemplazando un elemento con su inverso, reemplazando un elemento con el producto de sí mismo por otro elemento, y eliminando cualquier elemento igual a 1. Al aplicar estas transformaciones se forman conjuntos reducidos de Nielsen. Un conjunto reducido significa que ningún elemento puede ser multiplicado por otros elementos para cancelarse completamente. También existen conexiones entre las transformaciones de Nielsen y las palabras de Sturm. [1]
Un problema considerado en el estudio de la combinatoria sobre palabras en la teoría de grupos es el siguiente: para dos elementos , de un semigrupo , ¿ módulo las relaciones definitorias de y ? Post y Markov estudiaron este problema y determinaron que es indecidible , lo que significa que no hay un algoritmo posible que pueda responder a la pregunta en todos los casos (porque cualquier algoritmo de ese tipo podría codificarse en un problema de palabras que ese algoritmo no podría resolver). [1]
La cuestión de Burnside se demostró utilizando la existencia de una palabra infinita sin cubos . Esta pregunta pregunta si un grupo es finito si el grupo tiene un número definido de generadores y cumple los criterios para en el grupo. [1]
Muchos problemas verbales son indecidibles según el problema de correspondencia de Post . Dos homomorfismos cualesquiera con un dominio común y un codominio común forman una instancia del problema de correspondencia de Post, que pregunta si existe una palabra en el dominio tal que . Post demostró que este problema es indecidible; en consecuencia, cualquier problema verbal que pueda reducirse a este problema básico es igualmente indecidible. [1]
La combinatoria de palabras tiene aplicaciones en ecuaciones . Makanin demostró que es posible encontrar una solución para un sistema finito de ecuaciones, cuando las ecuaciones se construyen a partir de palabras. [1]
