En matemáticas , en las áreas de combinatoria e informática , una palabra Lyndon es una cadena no vacía que es estrictamente más pequeña en orden lexicográfico que todas sus rotaciones . Las palabras de Lyndon llevan el nombre del matemático Roger Lyndon , quien las investigó en 1954 y las llamó secuencias lexicográficas estándar . [1] Anatoly Shirshov introdujo las palabras de Lyndon en 1953 llamándolas palabras regulares . [2] Las palabras de Lyndon son un caso especial de las palabras de Hall.; casi todas las propiedades de las palabras de Lyndon son compartidas por las palabras de Hall.
Definiciones
Existen varias definiciones equivalentes.
Una palabra k -ary Lyndon de longitud n > 0 es una cadena de n caracteres sobre un alfabeto de tamaño k , y que es el único elemento mínimo en el orden lexicográfico en el conjunto múltiple de todas sus rotaciones. Ser la rotación singularmente más pequeña implica que una palabra de Lyndon difiere de cualquiera de sus rotaciones no triviales y, por lo tanto, es aperiódica. [3]
Alternativamente, una palabra w es una palabra de Lyndon si y solo si no está vacía y lexicográficamente estrictamente más pequeña que cualquiera de sus sufijos propios, es decir, w < v para todas las palabras no vacías v tales que w = uv y u no están vacías.
Otra caracterización es la siguiente: Una palabra Lyndon tiene la propiedad de que no está vacía y, siempre que se divide en dos subcadenas no vacías, la subcadena izquierda siempre es lexicográficamente menor que la subcadena derecha. Es decir, si w es una palabra Lyndon, y w = uv es cualquier factorización en dos subseries, con u y v entiende que no vacía, entonces u < v . Esta definición implica que una cadena w de longitud ≥ 2 es una palabra Lyndon si y solo si existen palabras Lyndon u y v tales que u < v y w = uv . [4] Aunque puede haber más de una opción de u y v con esta propiedad, existe una opción particular, llamada factorización estándar , en la que v es lo más largo posible. [5]
Enumeración
Las palabras de Lyndon sobre el alfabeto binario de dos símbolos {0,1}, ordenadas por longitud y luego lexicográficamente dentro de cada clase de longitud, forman una secuencia infinita que comienza
- 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...
La primera cadena que no pertenece a esta secuencia, "00", se omite porque es periódica (consta de dos repeticiones de la subcadena "0"); la segunda cadena omitida, "10", es aperiódica pero no es mínima en su clase de permutación, ya que puede permutarse cíclicamente a la cadena más pequeña "01".
La cadena vacía también cumple con la definición de una palabra Lyndon de longitud cero. Los números de palabras Lyndon binarias de cada longitud, comenzando con la longitud cero, forman la secuencia entera
Las palabras de Lyndon corresponden a representantes de la clase de collar aperiódico y, por lo tanto, se pueden contar con la función de conteo de collares de Moreau . [3] [6]
Generacion
Duval (1988) proporciona un algoritmo eficiente para enumerar las palabras de Lyndon de longitud como máximo n con un tamaño alfabético dado s en orden lexicográfico . Si w es una de las palabras de la secuencia, la siguiente palabra después de w se puede encontrar mediante los siguientes pasos:
- Repita los símbolos de w para formar una nueva palabra x de longitud exactamente n , donde el i- ésimo símbolo de x es el mismo que el símbolo en la posición ( i mod longitud ( w )) de w .
- Siempre que el símbolo final de x sea el último símbolo en el orden ordenado del alfabeto, elimínelo, produciendo una palabra más corta.
- Reemplace el último símbolo restante de x por su sucesor en el orden ordenado del alfabeto.
El peor de los casos para generar el sucesor de una palabra w mediante este procedimiento es O ( n ). Sin embargo, si las palabras que se generan se almacenan en una matriz de longitud n , y la construcción de x a partir de w se realiza agregando símbolos al final de w en lugar de hacer una nueva copia de w , entonces el tiempo promedio para generar el sucesor de w (asumiendo que cada palabra es igualmente probable) es constante. Por lo tanto, la secuencia de todas las palabras de Lyndon de longitud como máximo n se puede generar en un tiempo proporcional a la longitud de la secuencia. [7] Una fracción constante de las palabras en esta secuencia tienen una longitud exactamente n , por lo que se puede usar el mismo procedimiento para generar de manera eficiente palabras con una longitud exactamente n o palabras cuya longitud divide n , al filtrar las palabras generadas que no se ajustan a estas Criterios.
Factorización estándar
De acuerdo con el teorema de Chen-Fox-Lyndon , cada cadena puede formarse de una manera única concatenando una secuencia de palabras de Lyndon, de tal manera que las palabras de la secuencia no crezcan lexicográficamente. [8] La palabra Lyndon final en esta secuencia es el sufijo lexicográficamente más pequeño de la cadena dada. [9] Una factorización en una secuencia no creciente de palabras Lyndon (la denominada factorización Lyndon) se puede construir en tiempo lineal . [9] Las factorizaciones de Lyndon se pueden utilizar como parte de una variante biyectiva de la transformada de Burrows-Wheeler para la compresión de datos , [10] y en algoritmos para la geometría digital . [11]
Tales factorizaciones se pueden escribir (de forma única) como árboles binarios finitos, con las hojas etiquetadas por el alfabeto, con cada rama hacia la derecha dada por la palabra Lyndon final en la secuencia. [12] Estos árboles a veces se denominan corchetes estándar y se pueden tomar como factorización de los elementos de un grupo libre o como elementos básicos para un álgebra de Lie libre . Estos árboles son un caso especial de árboles de Hall (como las palabras de Lyndon son un caso especial de palabras de Hall) y, de la misma manera, las palabras de Hall proporcionan un orden estándar, llamado proceso de recolección de conmutadores para grupos y base para álgebras de Lie. [13] [14] [15] De hecho, proporcionan una construcción explícita para los conmutadores que aparecen en el teorema de Poincaré-Birkhoff-Witt necesarios para la construcción de álgebras envolventes universales .
Cada palabra de Lyndon puede entenderse como una permutación , la permutación estándar del sufijo .
Algoritmo de Duval
Duval (1983) desarrolló un algoritmo para encontrar la factorización estándar que se ejecuta en tiempo lineal y espacio constante. Repite una cadena tratando de encontrar una palabra Lyndon lo más larga posible. Cuando encuentra uno, lo agrega a la lista de resultados y procede a buscar la parte restante de la cadena. La lista de cadenas resultante es la factorización estándar de la cadena dada. A continuación, se presenta una descripción más formal del algoritmo.
Dada una cadena S de longitud N , se debe seguir con los siguientes pasos:
- Sea m el índice del símbolo-candidato que se agregará a los símbolos ya recopilados. Inicialmente, m = 1 (los índices de símbolos en una cadena comienzan desde cero).
- Sea k el índice del símbolo con el que compararíamos otros. Inicialmente, k = 0 .
- Mientras k y m son menos de N , comparar S [k] (el k símbolo-ésimo de la cadena S ) a S [m] . Hay tres posibles resultados:
- S [k] es igual a S [m] : agregue S [m] a los símbolos recopilados actualmente. Incrementar k y m .
- S [k] es menor que S [m] : si agregamos S [m] a los símbolos recopilados actualmente, obtendremos una palabra Lyndon. Pero todavía no podemos agregarlo a la lista de resultados porque puede ser solo una parte de una palabra Lyndon más grande. Por lo tanto, simplemente incremente my establezca k en 0 para que el siguiente símbolo se compare con el primero de la cadena.
- S [k] es mayor que S [m] : si agregamos S [m] a los símbolos recopilados actualmente, no será ni una palabra de Lyndon ni un posible comienzo de una. Por lo tanto, agregue los primeros símbolos recopilados de mk a la lista de resultados, elimínelos de la cadena, establezca m en 1 y k en 0 para que apunten al segundo y primer símbolo de la cadena, respectivamente.
- Cuando m> N , es esencialmente lo mismo que encontrar menos infinito, por lo tanto, agregue los primeros mk símbolos recopilados a la lista de resultados después de eliminarlos de la cadena, establezca m en 1 y k en 0, y regrese al paso anterior.
- Agregue S a la lista de resultados.
Conexión a las secuencias de Bruijn
Si se concatenan, en orden lexicográfico, todas las palabras de Lyndon que tienen una longitud que divide un número dado n , el resultado es una secuencia de Bruijn , una secuencia circular de símbolos tal que cada secuencia de longitud posible n aparece exactamente una vez como una de sus subsecuencias contiguas. Por ejemplo, la concatenación de las palabras binarias de Lyndon cuya longitud divide cuatro es
- 0 0001 0011 01 0111 1
Esta construcción, junto con la generación eficiente de palabras Lyndon, proporciona un método eficiente para construir una secuencia de Bruijn particular en tiempo lineal y espacio logarítmico . [dieciséis]
Propiedades y aplicaciones adicionales
Las palabras de Lyndon tienen una aplicación a la descripción de álgebras de Lie libres , al construir una base para la parte homogénea de un grado dado; esta fue la motivación original de Lyndon para introducir estas palabras. [4] Las palabras de Lyndon pueden entenderse como un caso especial de conjuntos de Hall . [4]
Para primo p , el número de polinomios mónicos irreducibles de grado d sobre el campoes el mismo que el número de palabras de Lyndon de longitud d en un alfabeto de p símbolos; pueden colocarse en correspondencia explícita. [17]
Un teorema de Radford establece que un álgebra aleatoria sobre un campo de característica 0 puede verse como un álgebra polinomial sobre las palabras de Lyndon. Más precisamente, dejar que A sea un alfabeto, dejar que k sea un cuerpo de característica 0 (o, más en general, un conmutativa ℚ-álgebra), y dejar que R sea el libre no conmutativo k -algebra k ⟨ x un | un ∈ A ⟩ . Las palabras sobre A pueden identificarse con los "monomios no conmutativos" (es decir, productos de x a ) en R ; es decir, identificamos una palabra ( a 1 , a 2 , ..., a n ) con el monomio x a 1 x a 2 ... x a n . Por lo tanto, las palabras más de A forman una k base espacio-vector de R . Entonces, se define un producto aleatorio en R ; este es un producto k -bilineal, asociativo y conmutativo, que se denota por ø, y que en las palabras se puede definir recursivamente por
- 1 ø v = v para cualquier palabra v ;
- u ø 1 = u para cualquier palabra u ;
- ua ш vb = ( u ш vb ) a + ( ua ш v ) b para cualquier a , b ∈ A y cualquier palabra u y v .
El álgebra aleatoria en el alfabeto A se define como el grupo aditivo R dotado de ø como multiplicación. El teorema de Radford [18] ahora establece que las palabras de Lyndon son elementos algebraicamente independientes de esta álgebra aleatoria, y la generan; por lo tanto, el álgebra aleatoria es isomorfa a un anillo polinomial sobre k , con los indeterminados correspondientes a las palabras de Lyndon. [18]
Ver también
- Rotación de cuerda mínima lexicográficamente
- Palabra mórfica
- Palabra sturmian
- Collar (combinatoria)
Notas
- ^ Lyndon (1954) .
- ^ Shirshov (1953) .
- ↑ a b Berstel y Perrin (2007) ; Melançon (2001) .
- ↑ a b c Melançon (2001) .
- ^ Berstel y Perrin (2007) .
- ^ Ruskey (2003) proporciona detalles de estos recuentos de palabras de Lyndon y varios conceptos relacionados.
- ^ Berstel y Pocchiola (1994) .
- ↑ Melançon (2001) . Berstel y Perrin (2007) escriben que, aunque esto se atribuye comúnmente a Chen, Fox y Lyndon (1958) , y se deriva de los resultados de ese artículo, no se declaró explícitamente hasta Schützenberger (1965) . Fue formulado explícitamente por Shirshov (1958) , véase Schützenberger y Sherman (1963) .
- ↑ a b Duval (1983) .
- ^ Gil y Scott (2009) ; Kufleitner (2009) .
- ^ Brlek y col. (2009) .
- ^ Amy Glen, " Combinatoria de Lyndon Words " (2012)
- ^ Guy Melançon, (1992) " Combinatoria de árboles Hall y palabras Hall ", Diario de teoría combinatoria , 59A (2) págs. 285-308.
- ^ Guy Melançon y Christophe Reutenauer (1989), "Palabras de Lyndon, álgebras libres y barajas", Canadian Journal of Mathematics . 41 , núm. 4, págs. 577-591.
- ^ Christophe Hohlweg y Christophe Reutenauer, " Palabras de Lyndon, permutaciones y árboles ", (2003) LaCIM
- ↑ Según Berstel & Perrin (2007) , la secuencia generada de esta manera fue descrita por primera vez (con un método de generación diferente) por Martin (1934) , y la conexión entre ella y las palabras de Lyndon fue observada por Fredricksen & Maiorana (1978) .
- ^ Solomon W. Golomb (1969) "Polinomios irreducibles, códigos de sincronización, collares primitivos y álgebra ciclotómica", Proc. Conf Matemáticas combinatorias y sus aplicaciones , págs. 358--370 (Universidad de Carolina del Norte).
- ↑ a b Radford (1979)
Referencias
- Berstel, Jean; Perrin, Dominique (2007), "Los orígenes de la combinatoria en palabras" (PDF) , European Journal of Combinatorics , 28 (3): 996–1022, doi : 10.1016 / j.ejc.2005.07.019 , MR 2300777.
- Berstel, J .; Pocchiola, M. (1994), "Costo promedio del algoritmo de Duval para generar palabras de Lyndon" (PDF) , Informática teórica , 132 (1–2): 415–425, doi : 10.1016 / 0304-3975 (94) 00013- 1 , MR 1290554.
- Brlek, S .; Lachaud, J.-O .; Provenzal, X .; Reutenauer, C. (2009), "Lyndon + Christoffel = digitally convex" (PDF) , Reconocimiento de patrones , 42 (10): 2239–2246, doi : 10.1016 / j.patcog.2008.11.010.
- Chen, K.-T .; Fox, RH ; Lyndon, RC (1958), "Cálculo diferencial libre. IV. Los grupos de cocientes de la serie central inferior", Annals of Mathematics , 2nd Ser., 68 (1): 81–95, doi : 10.2307 / 1970044 , JSTOR 1970044 , Señor 0102539.
- Duval, Jean-Pierre (1983), "Factorizar palabras sobre un alfabeto ordenado", Journal of Algorithms , 4 (4): 363–381, doi : 10.1016 / 0196-6774 (83) 90017-2.
- Duval, Jean-Pierre (1988), "Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée", Theoretical Computer Science (en francés), 60 (3): 255-283, doi : 10.1016 / 0304-3975 (88) 90113-2 , MR 0979464.
- Fredricksen, Harold; Maiorana, James (1978), "Collares de cuentas en k colores y secuencias k -ary de Bruijn", Discrete Mathematics , 23 (3): 207-210, doi : 10.1016 / 0012-365X (78) 90002-X , MR 0523071.
- Gil, J .; Scott, DA (2009), Una transformación de clasificación de cadenas biyectiva (PDF).
- Kufleitner, Manfred (2009), "Sobre variantes biyectivas de la transformada de Burrows-Wheeler ", en Holub, Jan; Žďárek, Jan (eds.), Prague Stringology Conference , págs. 65–69, arXiv : 0908.0239 , Bibcode : 2009arXiv0908.0239K.
- 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
- Lyndon, RC (1954), "On Burnside's problem", Transactions of the American Mathematical Society , 77 (2): 202-215, doi : 10.2307 / 1990868 , JSTOR 1990868 , MR 0064049.
- Martin, MH (1934), "Un problema en los arreglos", Boletín de la American Mathematical Society , 40 (12): 859–864, doi : 10.1090 / S0002-9904-1934-05988-3 , MR 1562989.
- Melançon, G. (2001) [1994], "Lyndon word" , Enciclopedia de Matemáticas , EMS Press
- Ruskey, Frank (2003), Información sobre collares, palabras de Lyndon, secuencias de De Bruijn , archivado desde el original el 2 de octubre de 2006.
- Schützenberger, diputado; Sherman, S (1963), "Sobre un producto formal sobre las clases conjugadas en un grupo libre", J. Math. Anal. Apl. , 7 (3): 482–488, doi : 10.1016 / 0022-247X (63) 90070-2 , MR 0158002.
- Schützenberger, MP (1965), "On a factorisation of free monoids", Proceedings of the American Mathematical Society , 16 (1): 21-24, doi : 10.2307 / 2033993 , JSTOR 2033993 , MR 0170971.
- Shirshov, AI (1953), "Subálgebras de álgebras de Lie libres", Mat. Sbornik , nueva serie, 33 (75): 441–452, MR 0059892
- Shirshov, AI (1958), "Sobre anillos de mentira libres", Mat. Sbornik , nueva serie, 45 (87): 113-122, MR 0099356
- Radford, David E. (1979), "Una base de anillo natural para el álgebra aleatoria y una aplicación a esquemas de grupo", Journal of Algebra , 58 (2): 432–454, doi : 10.1016 / 0021-8693 (79) 90171 -6.