En matemáticas , una factorización de un monoide libre es una secuencia de subconjuntos de palabras con la propiedad de que cada palabra en el monoide libre puede escribirse como una concatenación de elementos extraídos de los subconjuntos. El teorema de Chen- Fox - Lyndon establece que las palabras de Lyndon proporcionan una factorización. El teorema de Schützenberger relaciona la definición en términos de una propiedad multiplicativa con una propiedad aditiva. [ se necesita aclaración ]
Sea A * el monoide libre en un alfabeto A. Sea X i una secuencia de subconjuntos de A * indexados por un conjunto de índices I totalmente ordenado . Una factorización de una palabra w en A * es una expresión
con y . Algunos autores invierten el orden de las desigualdades.
Una palabra Lyndon sobre un alfabeto A totalmente ordenado es una palabra que lexicográficamente tiene menos que todas sus rotaciones. [1] El teorema de Chen-Fox-Lyndon establece que cada cadena puede formarse de una manera única concatenando una secuencia lexicográficamente no creciente de palabras de Lyndon. Por lo tanto, tomando X l como el conjunto singleton { l } para cada palabra de Lyndon l , con el conjunto de índices L de palabras de Lyndon ordenadas lexicográficamente, obtenemos una factorización de A * . [2] Esta factorización se puede encontrar en tiempo lineal y espacio constante mediante el algoritmo de Duval. [3] El algoritmo [4] en código Python es:
def chen_fox_lyndon_factorization ( s : lista [ int ]) -> lista [ int ]: """Factorización monoide usando el teorema de Chen-Fox-Lyndon. Args: s: una lista de números enteros Devuelve: una lista de números enteros """ n = len ( s ) factorización = [] i = 0 while i < n : j , k = i + 1 , i while j < n y s [ k ] <= s [ j ]: si s [ k ] < s [ j ]: k = i else : k += 1 j += 1 mientras i <= k : factorización agregar ( s [ i : i + j - k ] ) i += . j - k factorización de retorno El conjunto Hall proporciona una factorización. [5] De hecho, las palabras de Lyndon son un caso especial de las palabras de Hall. El artículo sobre las palabras de Hall proporciona un esbozo de todos los mecanismos necesarios para establecer una prueba de esta factorización.
Una bisección de un monoide libre es una factorización con solo dos clases X 0 , X 1 . [6]
Ejemplos:
Si X , Y son conjuntos disjuntos de palabras no vacías, entonces ( X , Y ) es una bisección de A * si y solo si [7]
Como consecuencia, para cualquier partición P , Q de A + hay una bisección única ( X , Y ) con X un subconjunto de P e Y un subconjunto de Q. [8]
Este teorema establece que una secuencia X i de subconjuntos de A * forma una factorización si y sólo si se cumplen dos de las tres afirmaciones siguientes:
