La combinatoria de palabras es un campo bastante nuevo de las matemáticas , que se deriva de la combinatoria , que se centra en el estudio de las palabras y los lenguajes formales . El sujeto observa letras o símbolos y las secuencias que forman. La combinatoria de palabras afecta a diversas áreas del 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 de Axel Thue a principios del siglo XX. Él y sus colegas observaron patrones dentro de las palabras y trataron de explicarlos. Con el paso del tiempo, la combinatoria de palabras se volvió útil en el estudio de algoritmos y codificación . Condujo a avances en álgebra abstracta y a responder preguntas abiertas.
La combinatoria es un área de las matemáticas discretas . La matemática discreta es el estudio de estructuras contables. Estos objetos tienen un principio y un fin definidos. El estudio de objetos enumerables es lo opuesto a disciplinas como el análisis , donde se estudia el cálculo y las estructuras infinitas . La combinatoria estudia cómo contar estos objetos utilizando varias representaciones. La combinatoria de palabras es un desarrollo reciente en este campo que se centra en el estudio de palabras y 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 gran público como alfabeto . Por ejemplo, la palabra “enciclopedia” es una secuencia de símbolos del 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 era de esperar, 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] Nuevamente mirando el ejemplo "enciclopedia", ya que enciclopedia tiene doce letras. La idea de factorizar números grandes se puede aplicar a palabras, donde un factor de una palabra es un bloque de símbolos consecutivos. [1] Por tanto, "cíclope" es un factor de "enciclopedia".
Además de examinar las secuencias en sí mismas, otra área a considerar de la combinatoria de las 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 estar completos o no. Es posible codificar una palabra, ya que una palabra se construye mediante símbolos y codificar los datos mediante un árbol. [1] Esto proporciona una representación visual del objeto.
Los primeros libros de combinatoria sobre palabras que resumen los orígenes de la materia fueron escritos por un grupo de matemáticos que colectivamente se llamaban M. Lothaire . Su primer libro se publicó en 1983, cuando la combinatoria de palabras se generalizó. [1]
Uno de los principales contribuyentes al desarrollo de la combinatoria de las 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 libres de cuadrados . Las palabras sin cuadrados no tienen factores repetidos adyacentes. [1] Para aclarar, "comer" no está libre de cuadrados ya que "in" se repite consecutivamente, mientras que "servers" está libre de cuadrados, ya que 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 fue 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. Continúa en su segundo artículo demostrando una relación entre infinitas palabras sin superposiciones y palabras sin cuadrados. Toma palabras sin superposiciones que se crean usando dos letras diferentes y demuestra cómo se pueden transformar en palabras sin cuadrados de tres letras mediante 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 o regularidades inevitables fue Frank Ramsey en 1930. Su importante teorema establece que para los números enteros , existe un entero mínimo positivo tal que a pesar de que un gráfico completo esté coloreado con dos colores, siempre habrá Existe un subgrafo de color sólido de cada color. [1]
Otros contribuyentes al estudio de patrones inevitables incluyen a van der Waerden . Su teorema establece que si los números enteros positivos se dividen en clases, entonces existe una clase 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 los sesquipoderes . Para algunos patrones , un sesquipoder tiene la forma ,,, . Este es otro patrón, como los patrones sin cuadrados o inevitables. Coudrain y Schützenberger estudiaron principalmente estos sesquipoderes para aplicaciones de teoría de grupos . Además, Zimin demostró que los sesquipoderes son todos inevitables. Ya sea que aparezca todo el patrón o solo una parte del sesquipoder aparezca repetitivamente, 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 longitud de De Bruijn . Un collar de Bruijn contiene factores formados por palabras de longitud n sobre un cierto número de letras. Las palabras aparecen sólo una vez en el collar. [1]
En 1874, Baudot desarrolló el código que acabaría sustituyendo al código Morse aplicando la teoría de los collares binarios de De Bruijn. El problema continuó desde Sainte-Marie hasta Martin en 1934, quien comenzó a buscar algoritmos para formar palabras con la estructura de De Bruijn. Luego, Posthumus trabajó en él en 1943. [1]
Posiblemente el resultado más aplicado en combinatoria de palabras sea la jerarquía de Chomsky , desarrollada por Noam Chomsky . Estudió 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 jerarquía lingüística . Los cuatro niveles son: regular , libre de contexto , sensible al contexto y enumerable computable o sin restricciones. [2] Regular es el menos complejo, mientras que computablemente enumerable es el más complejo. Si bien su trabajo surgió de la combinatoria de las 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 las palabras. Existen varias definiciones equivalentes de palabras sturmianas. Por ejemplo, una palabra infinita es sturmiana si y sólo si tiene distintos factores de longitud , para cada número entero no negativo . [1]
Una palabra Lyndon es una palabra de un alfabeto determinado que está escrita en su forma más simple y ordenada de su respectiva clase de conjugación . Las palabras de Lyndon son importantes porque para cualquier palabra de Lyndon determinada , existen palabras de Lyndon y , con ,. Además, existe un teorema de Chen, Fox y Lyndon que establece que cualquier palabra tiene una factorización única de las palabras de Lyndon, donde las palabras de factorización no son crecientes . Debido a esta propiedad, las palabras de Lyndon se utilizan para estudiar álgebra , específicamente teoría de grupos . Forman la base de la idea de conmutadores . [1]
Cobham contribuyó con un trabajo que relaciona el trabajo de Eugène Prouhet con autómatas finitos . Un gráfico matemático está formado por aristas y nodos . En los autómatas finitos, los bordes están etiquetados con una letra del alfabeto. Para usar el gráfico, se comienza en un nodo y se viaja a lo largo de los bordes hasta llegar al nodo final. El camino recorrido a lo largo del gráfico forma la palabra. Es un gráfico 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. Específicamente, se necesita una curva cerrada en un plano . Si la curva sólo 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 notó 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 de palabras en teoría de grupos con su trabajo publicado en 1882 y 1883. Comenzó utilizando palabras como elementos de grupo. Lagrange también contribuyó en 1771 con su trabajo sobre grupos de permutación . [1]
Un aspecto de la combinatoria de palabras estudiadas en teoría de grupos son las palabras reducidas. Un grupo se construye con palabras de algún alfabeto incluyendo generadores y elementos inversos , excluyendo factores que aparecen de la forma aā o āa, para alguna a en el alfabeto. Las palabras reducidas se forman cuando los factores aā, āa se usan para cancelar elementos hasta alcanzar 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 por su inverso, reemplazando un elemento por el producto de sí mismo y otro elemento, y eliminando cualquier elemento igual a 1. Aplicando estas transformaciones de Nielsen se forman conjuntos reducidos. Un conjunto reducido significa que ningún elemento puede multiplicarse por otros elementos para cancelarse por completo. También hay conexiones entre las transformaciones de Nielsen y las palabras de Sturm. [1]
Un problema considerado en el estudio de la combinatoria de palabras en teoría de grupos es el siguiente: para dos elementos , de un semigrupo , hace módulo las relaciones definitorias de y . Post y Markov estudiaron este problema y lo determinaron indecidible , lo que significa que no existe ningún algoritmo posible que pueda responder la pregunta en todos los casos (porque cualquier algoritmo de este tipo podría codificarse en un problema escrito que ese algoritmo no podría resolver). [1]
La pregunta 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 con los criterios , para en el grupo. [1]
Muchos problemas planteados son indecidibles según el problema de correspondencia postal . Dos homomorfismos cualesquiera con un dominio común y un codominio común forman una instancia del problema de correspondencia postal, que pregunta si existe una palabra en el dominio tal que . Post demostró que este problema es indecidible; en consecuencia, cualquier problema escrito 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]
