palabra lyndon

Cadena que es estrictamente más pequeña en orden lexicográfico que todas sus rotaciones

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 Lyndon llevan el nombre del matemático Roger Lyndon , quien las investigó en 1954, llamándolas secuencias lexicográficas estándar . ^[1] Anatoly Shirshov introdujo las palabras Lyndon en 1953 llamándolas palabras regulares . ^[2] Las palabras de Lyndon son un caso especial de 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 Lyndon -aria de longitud es una cadena de caracteres sobre un alfabeto de tamaño , y que es el elemento mínimo único 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] ${\displaystyle k}$ ${\displaystyle n>0}$ ${\displaystyle n}$ ${\displaystyle k}$

Alternativamente, una palabra es una palabra Lyndon si y sólo si no está vacía y lexicográficamente es estrictamente más pequeña que cualquiera de sus sufijos adecuados, es decir, para todas las palabras no vacías tales como y no está vacía. ${\displaystyle w}$ ${\displaystyle w<v}$ ${\displaystyle v}$ ${\displaystyle w=uv}$ ${\displaystyle u}$

Otra caracterización es la siguiente: una palabra Lyndon tiene la propiedad de no estar 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 es una palabra de Lyndon y es cualquier factorización en dos subcadenas, y se entiende que no está vacía, entonces . Esta definición implica que una cadena de longitud es una palabra Lyndon si y sólo si existen palabras Lyndon y tales que y . ^[4] Aunque puede haber más de una elección de y con esta propiedad, existe una elección particular, llamada factorización estándar , en la que es lo más larga posible. ^[5] ${\displaystyle w}$ ${\displaystyle w=uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u<v}$ ${\displaystyle w}$ ${\displaystyle \geq 2}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u<v}$ ${\displaystyle w=uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$

Enumeración

Las palabras 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 palabra Lyndon de longitud cero. Los números de palabras Lyndon binarias de cada longitud, comenzando con la longitud cero, forman la secuencia entera

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (secuencia A001037 en el OEIS )

Las palabras de Lyndon corresponden a representantes de la clase de collares aperiódicos y, por lo tanto, pueden contarse con la función de conteo de collares de Moreau . ^{[3] [6]}

Generación

Duval (1988) proporciona un algoritmo eficaz para enumerar en orden lexicográfico las palabras Lyndon de longitud máxima con un tamaño de alfabeto determinado . Si es una de las palabras de la secuencia, la siguiente palabra se puede encontrar siguiendo los siguientes pasos: ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle w}$ ${\displaystyle w}$

1. Repítalo y truncarlo a una nueva palabra de longitud exacta . ${\displaystyle w}$ ${\displaystyle x}$ ${\displaystyle n}$
2. Siempre que el símbolo final de sea el último símbolo en el orden del alfabeto, elimínelo y se producirá una palabra más corta. ${\displaystyle x}$
3. Reemplace el último símbolo restante de por su sucesor en el orden del alfabeto. ${\displaystyle x}$

Por ejemplo, supongamos que hemos generado palabras Lyndon binarias de longitud hasta 7 y hemos generado hasta , entonces los pasos son: ${\displaystyle w=00111}$

1. Repetir y truncar para obtener ${\displaystyle x=00111\;00{\cancel {111}}}$
2. Como el último símbolo es 0, no es el símbolo final.
3. Incrementa el último símbolo para obtener . ${\displaystyle x=00111\;01}$

El peor momento para generar el sucesor de una palabra mediante este procedimiento es . Sin embargo, si las palabras que se generan se almacenan en una matriz de longitud y la construcción de from se realiza agregando símbolos al final de en lugar de hacer una nueva copia de , entonces el tiempo promedio para generar el sucesor de (suponiendo que cada palabra es igualmente probable) es constante. Por lo tanto, la secuencia de todas las palabras Lyndon de longitud como máximo se puede generar en un tiempo proporcional a la longitud de la secuencia. ^[7] Una fracción constante de las palabras en esta secuencia tiene una longitud exacta , por lo que se puede utilizar el mismo procedimiento para generar eficientemente palabras de longitud exacta o palabras cuya longitud se divide , filtrando las palabras generadas que no se ajustan a estos criterios. ${\displaystyle w}$ ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Factorización estándar

Según 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 sean crecientes lexicográficamente. ^[8] La última palabra Lyndon en esta secuencia es el sufijo lexicográficamente más pequeño de la cadena dada. ^[9] Se puede construir una factorización en una secuencia no creciente de palabras Lyndon (la llamada factorización Lyndon) 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 geometría digital . ^[11]

Estas factorizaciones se pueden escribir (exclusivamente) como árboles binarios finitos, con las hojas etiquetadas por el alfabeto y cada rama hacia la derecha dada por la última palabra de Lyndon en la secuencia. ^[12] Estos árboles a veces se denominan corchetes estándar y pueden tomarse como factorización de los elementos de un grupo libre o como elementos base para un álgebra de Lie libre . Estos árboles son un caso especial de árboles de Hall (así 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 recopilación de conmutadores para grupos y base para las álgebras de Lie. ^[13] 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. Itera sobre 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 resultante de cadenas es la factorización estándar de la cadena dada. A continuación se incluye una descripción más formal del algoritmo.

Dada una cadena S de longitud N , se deben proceder con los siguientes pasos:

1. Sea m el índice del símbolo candidato que se agregará a los símbolos ya recopilados. Inicialmente, m = 1 (los índices de los símbolos en una cadena comienzan desde cero).
2. Sea k el índice del símbolo con el que compararíamos otros. Inicialmente, k = 0 .
3. Si bien k y m son menores que N , compare S[k] (el k -ésimo símbolo de la cadena S ) con S[m] . Hay tres resultados posibles:
   1. S[k] es igual a S[m] : agregue S[m] a los símbolos recopilados actualmente. Incremento k y m .
   2. 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 m y establezca k en 0 para que el siguiente símbolo se compare con el primero de la cadena.
   3. 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 por mk a la lista de resultados, elimínelos de la cadena, establezca m en 1 yk en 0 para que apunten al segundo y primer símbolo de la cadena respectivamente.
4. Cuando m > N , es esencialmente lo mismo que encontrar menos infinito, por lo tanto, agregue los primeros símbolos mk 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.
5. Agregue S a la lista de resultados.

Conexión con las secuencias de De Bruijn

Si se concatenan juntas, en orden lexicográfico, todas las palabras de Lyndon cuya longitud divide un número dado n , el resultado es una secuencia de De Bruijn , una secuencia circular de símbolos tal que cada posible secuencia de longitud n aparece exactamente una vez como una de sus subsecuencias contiguas. Por ejemplo, la concatenación de las palabras binarias Lyndon cuya longitud divide a cuatro es

0 0001 0011 01 0111 1

Esta construcción, junto con la generación eficiente de palabras de Lyndon, proporciona un método eficiente para construir una secuencia de De Bruijn particular en tiempo lineal y espacio logarítmico . ^[14]

Propiedades y aplicaciones adicionales

Las palabras de Lyndon tienen aplicación en la descripción de álgebras de Lie libres , en la construcción de una base para la parte homogénea de un grado determinado; ésta 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 p primo , el número de polinomios mónicos irreducibles de grado d sobre el campo es el mismo que el número de palabras Lyndon de longitud d en un alfabeto de p símbolos; se pueden colocar en correspondencia explícita. ^[15] ${\displaystyle \mathbb {F} _{p}}$

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, sea A un alfabeto, sea k un campo de característica 0 (o, más general, un álgebra conmutativa), y sea R el k -álgebra libre no conmutativa k ⟨ x _a | un ∈ UN ⟩ . Las palabras sobre A pueden entonces identificarse con los "monomios no conmutativos" (es decir, productos de x _a ) en R ; es decir, identificamos una palabra ( a ₁ , a ₂ ,..., an ₎ con el monomio x _{a 1} x _{a 2} ... x _{a n} . Por tanto, las palabras sobre A forman una base de espacio vectorial k 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 puede definirse recursivamente por ${\displaystyle \mathbb {Q} }$

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 del alfabeto A se define como el grupo aditivo R dotado de ш como multiplicación. El teorema de Radford ^[16] establece ahora que las palabras de Lyndon son elementos algebraicamente independientes de este álgebra aleatoria y la generan; por tanto, el álgebra aleatoria es isomorfa a un anillo polinómico sobre k , y los indeterminados corresponden a las palabras de Lyndon. ^[dieciséis]

Ver también

• Rotación de cadenas lexicográficamente mínima
• palabra mórfica
• palabra sturmiana
• Collar (combinatoria)

Notas

1. Lyndon (1954).
2. Shirshov (1953).
3. Berstel y Perrin (2007); Melançon (2001).
4. Melançon (2001).
5. Berstel y Perrin (2007).
6. Ruskey (2003) proporciona detalles de estos recuentos de palabras de Lyndon y varios conceptos relacionados.
7. Berstel y Pocchiola (1994).
8. Melanzón (2001). Berstel y Perrin (2007) escriben que, aunque esto se atribuye comúnmente a Chen, Fox y Lyndon (1958), y se desprende de los resultados de ese artículo, no se afirmó explícitamente hasta Schützenberger (1965). Fue formulado explícitamente por Shirshov (1958), véase Schützenberger y Sherman (1963).
9. Duval (1983).
10. Gil y Scott (2009); Kufleitner (2009).
11. Brlek y col. (2009).
12. Glen (2012).
13. Melanzón (1992); Melancon y Reutenauer (1989); Hohlweg y Reutenauer (2003)
14. Según Berstel y 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 Fredricksen y Maiorana (1978) observaron la conexión entre ella y las palabras de Lyndon.
15. Golomb (1969).
16. Radford (1979)

Referencias

• Berstel, Jean; Perrin, Dominique (2007), "Los orígenes de la combinatoria de las 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 Lyndon" (PDF) , Ciencias de la Computación Teórica , 132 (1–2): 415–425, doi : 10.1016/0304-3975(94)00013- 1 , señor  1290554.
• Brlek, S.; Lachaud, J.-O.; Provenzal, X.; Reutenauer, C. (2009), "Lyndon + Christoffel = digitalmente convexo" (PDF) , Reconocimiento de patrones , 42 (10): 2239–2246, Bibcode :2009PatRe..42.2239B, doi :10.1016/j.patcog.2008.11. 010.
• Chen, K.-T.; Fox, RH ; Lyndon, RC (1958), "Cálculo diferencial libre. IV. Los grupos 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), "Factorización de 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 sección des clases de conjugaison et arbre des mots de Lyndon de longueur bornée", Ciencias de la Computación Teórica (en francés), 60 (3): 255–283, doi :10.1016 /0304-3975(88)90113-2, SEÑOR  0979464.
• Fredricksen, Harold; Maiorana, James (1978), "Collares de cuentas en k colores y secuencias k -ary de Bruijn", Matemáticas discretas , 23 (3): 207–210, doi : 10.1016/0012-365X(78)90002-X , SEÑOR  0523071.
• Gil, J.; Scott, DA (2009), Una transformación de clasificación de cadenas biyectivas (PDF).
• Glen, Amy (2012), "Combinatoria de palabras de Lyndon" (PDF) , miniconferencia: combinatoria, representaciones y estructura del tipo Lie , Universidad de Melbourne
• Golomb, Solomon W. (1969), "Polinomios irreducibles, códigos de sincronización, collares primitivos y álgebra ciclotómica", en Bose, RC; Dowling, TA (eds.), Matemáticas combinatorias y sus aplicaciones: Actas de la conferencia celebrada en la Universidad de Carolina del Norte en Chapel Hill, del 10 al 14 de abril de 1967 , serie de monografías sobre probabilidad y estadística de la Universidad de Carolina del Norte, vol. 4, Prensa de la Universidad de Carolina del Norte, págs. 358–370, ISBN 9780807878200, OCLC  941682678
• Hohlweg, Christophe; Reutenauer, Christophe (2003), "Palabras, permutaciones y árboles de Lyndon" (PDF) , Ciencias de la Computación Teórica , 307 (1): 173–8, doi :10.1016/S0304-3975(03)00099-9
• Kufleitner, Manfred (2009), "Sobre las variantes biyectivas de la transformada de Burrows-Wheeler ", en Holub, Jan; Žďárek, Jan (eds.), Conferencia de Stringología de Praga, págs. 65–69, arXiv : 0908.0239 , Bibcode :2009arXiv0908.0239K.
• Lothaire, M. (1983), Combinatoria de palabras, Enciclopedia de las Matemáticas y sus Aplicaciones, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., ISBN 978-0-201-13516-9, señor  0675953
• Lyndon, RC (1954), "Sobre el problema de Burnside", Transactions of the American Mathematical Society , 77 (2): 202–215, doi :10.2307/1990868, JSTOR  1990868, MR  0064049.
• Martin, MH (1934), "Un problema de arreglos", Boletín de la Sociedad Matemática Estadounidense , 40 (12): 859–864, doi : 10.1090/S0002-9904-1934-05988-3 , SEÑOR  1562989.
• Melançon, Guy (1992), "Combinatoria de árboles Hall y palabras Hall" (PDF) , Journal of Combinatorial Theory , Serie A, 59 (2): 285–308, doi : 10.1016/0097-3165(92)90070-B
• Melançon, G. (2001) [1994], "Lyndon word", Enciclopedia de Matemáticas , EMS Press
• Melançon, Guy; Reutenauer, Christophe (1989), "Palabras de Lyndon, álgebras y combinaciones aleatorias libres", Canadian Journal of Mathematics , 41 (4): 577–591, doi : 10.4153/CJM-1989-025-2 , S2CID  17395250
• 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", Journal of Mathematical Analysis and Applications , 7 (3): 482–488, doi : 10.1016/0022-247X(63)90070- 2 , señor  0158002.
• Schützenberger, MP (1965), "Sobre una factorización de monoides libres", Actas de la Sociedad Matemática Estadounidense , 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, SEÑOR  0059892
• Shirshov, AI (1958), "Sobre los anillos de mentira libres", Mat. Sbornik , nueva serie, 45 (87): 113–122, SEÑOR  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.