Palabra de 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 y ciencias de la computación , 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 reciben su 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 Lyndon son un caso especial de palabras Hall ; casi todas las propiedades de las palabras Lyndon son compartidas por las palabras 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 único elemento mínimo en el ordenamiento lexicográfico en el multiconjunto de todas sus rotaciones. Ser la rotación singularmente más pequeña implica que una palabra 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 solo si no está vacía y es lexicográficamente estrictamente más pequeña que cualquiera de sus sufijos propios, es decir, para todas las palabras no vacías tales que 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 que no está vacía y, siempre que se divida en dos subcadenas no vacías, la subcadena izquierda siempre es lexicográficamente menor que la subcadena derecha. Es decir, si es una palabra Lyndon, y es cualquier factorización en dos subcadenas, con y entendidos como no vacíos, entonces . Esta definición implica que una cadena de longitud es una palabra Lyndon si y solo si existen palabras Lyndon y tales que y . ^[4] Aunque puede haber más de una opción de y con esta propiedad, hay una opció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 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 (consiste en 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. La cantidad de palabras Lyndon binarias de cada longitud, comenzando con longitud cero, forma la secuencia de números enteros.

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (secuencia A001037 en la 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) ofrece un algoritmo eficiente para enumerar las palabras de Lyndon de longitud máxima con un tamaño de alfabeto determinado en orden lexicográfico . Si es una de las palabras de la secuencia, entonces la palabra siguiente se puede encontrar siguiendo los pasos siguientes: ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle w}$ ${\displaystyle w}$

1. Repítelo y truncalo a una nueva palabra con una longitud exactamente igual a . ${\displaystyle w}$ ${\displaystyle x}$ ${\displaystyle n}$
2. Siempre que el símbolo final sea el último símbolo en el orden ordenado del alfabeto, elimínelo y obtendrá una palabra más corta. ${\displaystyle x}$
3. Reemplace el símbolo final restante por su sucesor en el orden ordenado del alfabeto. ${\displaystyle x}$

Por ejemplo, supongamos que hemos generado las palabras binarias Lyndon 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. Dado que 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 tiempo posible 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 añadiendo símbolos al final de en lugar de haciendo una nueva copia de , entonces el tiempo medio 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 de esta secuencia tienen una longitud exactamente , por lo que se puede utilizar el mismo procedimiento para generar de forma eficiente palabras de longitud exactamente o palabras cuya longitud divida a , 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 Lyndon, de tal manera que las palabras en la secuencia no sean crecientes 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 llamada factorización Lyndon) se puede construir en tiempo lineal . ^[9] Las factorizaciones Lyndon se pueden usar como parte de una variante biyectiva de la transformada de Burrows-Wheeler para compresión de datos , ^[10] y en algoritmos para geometría digital . ^[11]

Tales factorizaciones pueden escribirse (únicamente) como árboles binarios finitos, con las hojas etiquetadas por el alfabeto, con cada rama hacia la derecha dada por la palabra final de Lyndon en la secuencia. ^[12] A estos árboles a veces se les llama corchetes estándar y pueden tomarse como factorización de los elementos de un grupo libre o como los elementos base 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 así, 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 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 necesario para la construcción de álgebras envolventes universales .

Cada palabra de Lyndon puede entenderse como una permutación , siendo el sufijo permutación estándar .

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 intentando encontrar la palabra Lyndon más larga posible. Cuando encuentra una, la 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 deben seguir los siguientes pasos:

1. Sea m el índice del candidato a símbolo que se añadirá a los símbolos ya recopilados. Inicialmente, m = 1 (los índices de símbolos en una cadena comienzan desde cero).
2. Sea k el índice del símbolo con el que compararemos otros. Inicialmente, k = 0.
3. Si k y m son menores que N , compare S [ k ] (el símbolo k -ésimo de la cadena S ) con S [ m ]. Hay tres resultados posibles:
   1. S [ k ] es igual a S [ m ]: agrega S [ m ] a los símbolos recopilados actualmente. Incrementa 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 no podemos agregarla a la lista de resultados todavía porque puede ser solo una parte de una palabra Lyndon más grande. Por lo tanto, solo incremente m y configure k en 0 para que el siguiente símbolo se compare con el primero en 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 Lyndon ni un posible comienzo de una. Por lo tanto, agregue los primeros m − k símbolos recopilados a la lista de resultados, elimínelos de la cadena, establezca m en 1 y k en 0 para que apunten al segundo y al 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 m − k 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.
5. Añade 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 Lyndon cuya longitud es divisoria de 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 es divisoria de 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 Bruijn particular en tiempo lineal y espacio logarítmico . ^[14]

Propiedades y aplicaciones adicionales

Las palabras de Lyndon tienen una 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 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 el primo p , el número de polinomios mónicos irreducibles de grado d sobre el cuerpo es el mismo que el número de palabras Lyndon de longitud d en un alfabeto de símbolos p ; se pueden colocar en correspondencia explícita. ^[15] ${\displaystyle \mathbb {F} _{p}}$

Un teorema de Radford establece que un álgebra aleatoria sobre un cuerpo de característica 0 puede verse como un álgebra polinómica sobre las palabras de Lyndon. Más precisamente, sea A un alfabeto, sea k un cuerpo de característica 0 (o, más general, un ℚ-álgebra conmutativa), y sea R la k -álgebra no conmutativa libre k ⟨ x _a | a ∈ A ⟩ . Las palabras sobre A pueden entonces identificarse con los "monomios no conmutativos" (es decir, productos de los x _a ) en R ; es decir, identificamos una palabra ( a ₁ , a ₂ ,..., a _n ) con el monomio x _{a 1} x _{a 2} ... x _{a n} . Por lo tanto, las palabras sobre A forman una base de espacio vectorial k de R . Entonces, un producto aleatorio se define en R ; Este es un producto k -bilineal, asociativo y conmutativo, que se denota por ш, y que en las palabras puede definirse 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 sobre el 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 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. ^[16]

Véase también

• Rotación de cuerdas mínima lexicográficamente
• Palabra mórfica
• Palabra de Sturmian
• Collar (combinatoria)

Notas

1. Lyndon (1954).
2. Shirshov (1953).
3. Berstel y Perrin (2007); Melançon (2001).
4. Melancón (2001).
5. Berstel y Perrin (2007).
6. Ruskey (2003) proporciona detalles de estos recuentos para las palabras de Lyndon y varios conceptos relacionados.
7. Berstel y Pocchiola (1994).
8. Melançon (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 trabajo, 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 otros (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 la conexión entre ésta y las palabras de Lyndon fue observada por Fredricksen y Maiorana (1978).
15. Golomb (1969).
16. 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 Lyndon" (PDF) , Theoretical Computer Science , 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 = 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 , 2.ª serie, 68 (1): 81–95, doi :10.2307/1970044, JSTOR  1970044, MR  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", Informática 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 de De Bruijn k -arias", 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 ordenamiento de cadenas biyectiva (PDF).
• Glen, Amy (2012), "Combinatoria de palabras de Lyndon" (PDF) , Miniconferencia: Combinatoria, representaciones y estructura del tipo de 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 de la Universidad de Carolina del Norte sobre probabilidad y estadística, vol. 4, University of North Carolina Press, págs. 358–370, ISBN 9780807878200, OCLC  941682678
• Hohlweg, Christophe; Reutenauer, Christophe (2003), "Palabras, permutaciones y árboles de Lyndon" (PDF) , Theoretical Computer Science , 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 Cuerdas de Praga, págs. 65–69, arXiv : 0908.0239 , Bibcode :2009arXiv0908.0239K.
• Lothaire, M. (1983), Combinatoria de palabras, Enciclopedia de matemáticas y sus aplicaciones, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., ISBN 978-0-201-13516-9, Sr.  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 en los arreglos", Boletín de la Sociedad Matemática Americana , 40 (12): 859–864, doi : 10.1090/S0002-9904-1934-05988-3 , MR  1562989.
• Melançon, Guy (1992), "Combinatoria de árboles de Hall y palabras de 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], "Palabra Lyndon", Enciclopedia de Matemáticas , EMS Press
• Melançon, Guy; Reutenauer, Christophe (1989), "Palabras de Lyndon, álgebras libres y barajas", Revista Canadiense de Matemáticas , 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, MP ; 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 , MR  0158002.
• Schützenberger, MP (1965), "Sobre una factorización de monoides libres", Actas de la 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 los anillos de Lie 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 los esquemas de grupo", Journal of Algebra , 58 (2): 432–454, doi : 10.1016/0021-8693(79)90171-6.