La combinatoria de palabras es un campo bastante nuevo de las matemáticas , derivado 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 varias á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 Thuea principios de 1900. É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 desarrollos en álgebra abstracta y a responder preguntas abiertas.
Definición
La combinatoria es un área de las matemáticas discretas . Las matemáticas discretas son el estudio de estructuras contables. Estos objetos tienen un principio y un final definidos. El estudio de objetos enumerables es lo contrario de disciplinas como el análisis , donde se estudian el cálculo y las estructuras infinitas . La combinatoria estudia cómo contar estos objetos usando 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 usan para comunicar información. [1]
Primero se debe explicar alguna 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 del alfabeto inglés , un conjunto finito de veintiséis letras. Dado que una palabra se puede describir como una secuencia, se pueden aplicar otras descripciones matemáticas básicas. El alfabeto es un conjunto , por lo que, como cabría esperar, el conjunto vacío es un subconjunto . En otras palabras, existe una palabra única de longitud cero. La longitud de la palabra se define por el número de símbolos que componen la secuencia y se denota por | w |. [1] Mirando de nuevo el ejemplo "enciclopedia", | w | = 12, ya que la 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 lo tanto, "cyclop" es un factor de "enciclopedia".
Además de examinar las secuencias en sí mismas, otra área a considerar de la combinatoria de 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 ruta o borde . 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 da una representación visual del objeto.
Contribuciones importantes
Los primeros libros de combinatoria sobre palabras que resumen los orígenes del tema fueron escritos por un grupo de matemáticos que colectivamente se hicieron llamar M. Lothaire . Su primer libro se publicó en 1983, cuando se generalizó la combinatoria de palabras. [1]
Patrones
Patrones dentro de las palabras
Un contribuyente principal al 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, "verano" no está libre de cuadrados ya que m se repite consecutivamente, mientras que "enciclopedia" no tiene cuadrados. Thue prueba su conjetura sobre la existencia de infinitas palabras sin cuadrados mediante sustituciones . Una sustitución es una forma de tomar un símbolo y reemplazarlo por una palabra. Utiliza esta técnica para describir su otra contribución, la secuencia Thue-Morse , o la 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. También demostró la existencia de una palabra sin superposición. Una palabra sin superposición es cuando, para dos símbolos xey, el patrón xyxyx no existe dentro de la palabra. Continúa en su segundo ensayo para demostrar una relación entre infinitas palabras sin superposición y palabras sin cuadrados. Toma palabras sin superposición que se crean con 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 inevitables , o regularidades, fue Frank Ramsey en 1930. Su teorema importante establece que para los enteros k, m≥2, existe un entero mínimo positivo R (k, m) tal que a pesar de cómo un completo El gráfico está coloreado con dos colores, siempre existirá un subgráfico 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 enteros positivos se dividen en k clases, entonces existe una clase c tal que c contiene una progresión aritmética de alguna 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 sesquipowers . Para algunos patrones x, y, z, un sesquipoder es de la forma x, xyx, xyxzxyx, .... Este es otro patrón como patrones sin cuadrados o inevitables. Coudrain y Schützenberger estudiaron principalmente estos sesquipopotencias para aplicaciones de teoría de grupos . Además, Zimin demostró que los sesquipoderes son inevitables. Ya sea que aparezca el patrón completo o solo una parte del sesquipower se muestre repetidamente, no es posible evitarlo. [1]
Patrones dentro de alfabetos
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 hay 2 2 n −1 - n collares binarios de Bruijn de 2 n 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 tomaría el lugar del código Morse al aplicar la teoría de los collares binarios de Bruijn. El problema continuó desde Sainte-Marie hasta Martin en 1934, quien comenzó a buscar algoritmos para formar palabras con la estructura de Bruijn. Luego fue trabajado por Posthumus en 1943. [1]
Jerarquía de idiomas
Posiblemente el resultado más aplicado en la 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 de extensión. 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: normal , libre de contexto , sensible al contexto , y computablemente enumerable 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 palabras, afectó drásticamente a otras disciplinas, especialmente a la informática . [3]
Tipos de palabras
Palabras sturmianas
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 Sturmian si y solo si tiene n + 1 factores distintos de longitud n, para cada entero no negativo n. [1]
Palabra Lyndon
Una palabra de Lyndon es una palabra sobre un alfabeto dado que está escrita en su forma más simple y ordenada fuera de su respectiva clase de conjugación . Las palabras de Lyndon son importantes porque para cualquier palabra de Lyndon dada x, existen palabras de Lyndon y y z, con y
Representación visual
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 . Con autómatas finitos, los bordes están etiquetados con una letra en un alfabeto. Para usar el gráfico, uno comienza en un nodo y viaja a lo largo de los bordes para llegar a un nodo final. El camino tomado a lo largo del gráfico forma la palabra. Es un gráfico finito porque hay un número contable de nodos y bordes, y solo una ruta 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 solo se cruza sobre sí misma un número finito de veces, entonces se etiquetan las intersecciones con una letra del alfabeto utilizado. Viajando a lo largo de la curva, la palabra se determina registrando cada letra a medida que se pasa 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]
Teoría de grupos
Walther Franz Anton von Dyck comenzó el trabajo de combinatoria sobre palabras en la teoría de grupos con su trabajo publicado en 1882 y 1883. Comenzó usando 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 que se estudia en la teoría de grupos son las palabras reducidas. Un grupo se construye con palabras en algún alfabeto que incluye generadores y elementos inversos , excluyendo factores que aparecen de la forma aā o āa, para algunos 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 por su inverso, reemplazando un elemento con el producto de sí mismo y otro elemento, y eliminando cualquier elemento igual a 1. Aplicando estas transformaciones se forman conjuntos reducidos de Nielsen. Un conjunto reducido significa que ningún elemento puede multiplicarse por otros elementos para cancelar completamente. También hay conexiones con las transformaciones de Nielsen con palabras sturmianas. [1]
Problemas considerados
Un problema considerado en el estudio de la combinatoria de palabras en la teoría de grupos es el siguiente: para dos elementos x, y de un semigrupo , ¿x = y módulo las relaciones definitorias de x e y? Post y Markov estudiaron este problema y lo determinaron indecidible . Indecidible significa que la teoría no se puede probar. [1]
La pregunta de Burnside se demostró mediante 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 x n = 1, para x en el grupo. [1]
Muchos problemas de palabras son indecidibles basados en el problema de correspondencia posterior . Dos homomorfismos cualesquiera con un dominio común y un codominio común forman una instancia del problema de correspondencia posterior, 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]
Otras aplicaciones
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]
Ver también
- Palabra de fibonacci
- Secuencia de Kolakoski
- Lema de Levi
- Palabra parcial
- Espacio de turno
- Métrica de palabras
- Problema verbal (computabilidad)
- Problema verbal (matemáticas)
- Problema verbal para grupos
- Celosía Young – Fibonacci
Referencias
- ^ a b c d e f g h i j k l m n o p q r s t u v w x y Berstel, Jean; Dominique Perrin (abril de 2007). "Los orígenes de la combinatoria sobre palabras". Revista europea de combinatoria . 28 (3): 996–1022. doi : 10.1016 / j.ejc.2005.07.019 .
- ^ a b Jäger, Gerhard; James Rogers (julio de 2012). "Teoría del lenguaje formal: refinando la jerarquía de Chomsky" . Philosophical Transactions de la Royal Society B . 367 (1598): 1956–1970. doi : 10.1098 / rstb.2012.0077 . PMC 3367686 . PMID 22688632 .
- ^ Morales-Bueno, Rafael; Baena-García, Manuel; Carmona-Cejudo, José M .; Castillo, Gladys (2010). "Contando factores para evitar palabras". Revista Electrónica de Matemáticas y Tecnología . 4 (3): 251.
Otras lecturas
- Los orígenes de la combinatoria en palabras , Jean Berstel, Dominique Perrin , European Journal of Combinatorics 28 (2007) 996–1022
- Combinatoria en palabras: un tutorial , Jean Berstel y Juhani Karhumäki. Toro. EUR. Assoc. Theor. Computación. Sci. EATCS, 79: 178–228, 2003.
- Combinatoria en palabras: un nuevo tema desafiante , Juhani Karhumäki.
- Choffrut, cristiano; Karhumäki, Juhani (1997). "Combinatoria de palabras". En Rozenberg, Grzegorz; Salomaa, Arto (eds.). Manual de lenguajes formales . 1 . Saltador. CiteSeerX 10.1.1.54.3135 . ISBN 978-3-540-60420-4.
- Lothaire, M. (1983), Combinatoria en palabras , Enciclopedia de las matemáticas y sus aplicaciones, 17 , Addison-Wesley Publishing Co., Reading, Mass., ISBN 978-0-201-13516-9, MR 0675953 , Zbl 0.514,20045
- Lothaire, M. (2002), Combinatoria algebraica de palabras , Enciclopedia de las matemáticas y sus aplicaciones, 90 , Cambridge University Press , ISBN 978-0-521-81220-7, MR 1905123 , Zbl 1001.68093
- "Palabras infinitas: autómatas, semigrupos, lógica y juegos", Dominique Perrin, Jean Éric Pin, Academic Press, 2004, ISBN 978-0-12-532111-2 .
- Lothaire, M. (2005), Combinatoria aplicada en palabras , Enciclopedia de las matemáticas y sus aplicaciones, 105 , Cambridge University Press , ISBN 978-0-521-84802-2, MR 2165687 , Zbl 1133.68067
- " Combinatoria algorítmica en palabras parciales ", Francine Blanchet-Sadri, CRC Press, 2008, ISBN 978-1-4200-6092-8 .
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009), Combinatoria sobre palabras. Palabras de Christoffel y repeticiones en palabras , CRM Monograph Series, 27 , Providence, RI: American Mathematical Society , ISBN 978-0-8218-4480-9, Zbl 1161.68043
- "Combinatoria de composiciones y palabras", Silvia Heubach , Toufik Mansour , CRC Press, 2009, ISBN 978-1-4200-7267-9 .
- "Ecuaciones de palabras y temas relacionados: 1er taller internacional, IWWERT '90, Tübingen, Alemania, 1 al 3 de octubre de 1990: actas", Editor: Klaus Ulrich Schulz, Springer, 1992, ISBN 978-3-540-55124-9
- " Joyas de la cadenaología: algoritmos de texto ", Maxime Crochemore, Wojciech Rytter , World Scientific, 2003, ISBN 978-981-02-4897-0
- Berthé, Valérie ; Rigo, Michel, eds. (2010). Combinatoria, autómatas y teoría de números . Enciclopedia de Matemáticas y sus Aplicaciones. 135 . Cambridge: Cambridge University Press . ISBN 978-0-521-51597-9. Zbl 1197.68006 .
- Berstel, Jean; Reutenauer, Christophe (2011). Serie racional no conmutativa con aplicaciones . Enciclopedia de las matemáticas y sus aplicaciones. 137 . Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0. Zbl 1250.68007 .
- "Patrones en permutaciones y palabras", Sergey Kitaev, Springer, 2011, ISBN 9783642173325
- "Módulo de distribución uno y aproximación diofántica", Yann Bugeaud, Cambridge University Press, 2012, ISBN 9780521111690
enlaces externos
- Página de Jean Berstel
- Página de Tero Harju
- La página de Guy Melançon