Lyndon palabra

En matemáticas , en las áreas de combinatoria e informática , una palabra de Lyndon es una cadena no vacía que es estrictamente menor en orden lexicográfico que todas sus rotaciones . Las palabras de Lyndon reciben su nombre del matemático Roger Lyndon , quien las investigó en 1954, denominándolas 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.

Existen varias definiciones equivalentes.

A${\displaystyle k}$-ary Lyndon palabra de longitud${\displaystyle n>0}$es un${\displaystyle n}$-cadena de caracteres sobre un alfabeto de tamaño${\displaystyle k}$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 de Lyndon difiere de cualquiera de sus rotaciones no triviales y, por lo tanto, es aperiódica. ^{[ 3 ]}

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

Otra caracterización es la siguiente: Una palabra de Lyndon tiene la propiedad de que no es vacía y, siempre que se divide en dos subcadenas no vacías, la subcadena izquierda es siempre lexicográficamente menor que la subcadena derecha. Es decir, si${\displaystyle w}$es una palabra de Lyndon y${\displaystyle w=uv}$es cualquier factorización en dos subcadenas, con${\displaystyle u}$y${\displaystyle v}$entendido como no vacío, entonces${\displaystyle u<v}$Esta definición implica que una cadena${\displaystyle w}$de longitud${\displaystyle \geq 2}$es una palabra de Lyndon si y solo si existen palabras de Lyndon${\displaystyle u}$y${\displaystyle v}$de tal manera que${\displaystyle u<v}$y${\displaystyle w=uv}$. ^{[ 4 ]} Aunque puede haber más de una opción de${\displaystyle u}$y${\displaystyle v}$Con esta propiedad, existe una elección particular, llamada factorización estándar , en la que${\displaystyle v}$es lo más largo posible. ^{[ 5 ]}

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 corta "01".

La cadena vacía también cumple la definición de una palabra de Lyndon de longitud cero. El número de palabras binarias de Lyndon 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 clases de collares aperiódicos y, por lo tanto, pueden contarse con la función de conteo de collares de Moreau . ^{[ 3 ] [ 6 ]}

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

1. Repetir${\displaystyle w}$y truncarlo a una nueva palabra.${\displaystyle x}$de longitud exactamente${\displaystyle n}$.
2. Siempre y cuando el símbolo final de${\displaystyle x}$es el último símbolo en el orden alfabético, elimínelo, produciendo una palabra más corta.
3. Reemplace el último símbolo restante de${\displaystyle x}$por su sucesor en el orden alfabético.

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

1. Repite y trunca 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 momento posible para generar el sucesor de una palabra.${\displaystyle w}$mediante este procedimiento es${\displaystyle O(n)}$Sin embargo, si las palabras que se generan se almacenan en una matriz de longitud${\displaystyle n}$y la construcción de${\displaystyle x}$de${\displaystyle w}$se realiza agregando símbolos al final de${\displaystyle w}$en lugar de hacer una nueva copia de${\displaystyle w}$, entonces el tiempo promedio para generar el sucesor de${\displaystyle w}$(suponiendo que cada palabra es igualmente probable) es constante. Por lo tanto, la secuencia de todas las palabras de Lyndon de longitud como máximo${\displaystyle n}$puede generarse 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${\displaystyle n}$, por lo que se puede utilizar el mismo procedimiento para generar eficientemente palabras de longitud exactamente${\displaystyle n}$o palabras cuya longitud divide${\displaystyle n}$, filtrando las palabras generadas que no se ajustan a estos criterios.

Según el teorema de Chen-Fox-Lyndon , toda cadena puede formarse de manera única concatenando una secuencia de palabras de Lyndon, de modo que las palabras de la secuencia sean lexicográficamente no crecientes. ^{[ 8 ]} La última palabra de Lyndon 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 de Lyndon (la llamada factorización de Lyndon) puede construirse en tiempo lineal . ^{[ 9 ]} Las factorizaciones de Lyndon pueden utilizarse 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 ]}

Tales factorizaciones pueden escribirse (de forma única) como árboles binarios finitos, con las hojas etiquetadas por el alfabeto, y cada rama 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 por lo tanto, 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 ]} 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 .

Si se concatenan, en orden lexicográfico, todas las palabras de Lyndon cuya longitud divide a 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 de 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 ]}

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

Un teorema de Radford afirma que un álgebra de permutación sobre un cuerpo 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 cuerpo de característica 0 (o, más general, un álgebra ℚ conmutativa ), y sea R el álgebra k 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 de permutación 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 cualesquiera a , b ∈ A y cualesquiera palabras u y v .

El álgebra de barajado sobre el alfabeto A se define como el grupo aditivo R dotado de ш como multiplicación. El teorema de Radford ^{[ 16 ]} establece que las palabras de Lyndon son elementos algebraicamente independientes de esta álgebra de barajado y la generan; por lo tanto, el álgebra de barajado es isomorfa a un anillo de polinomios sobre k , con las indeterminadas correspondientes a las palabras de Lyndon. ^{[ 16 ]}

• Rotación de cadena lexicográficamente mínima
• Palabra morfológica
• Palabra de Sturm
• Collar (combinatoria)