Factorización monoide

En matemáticas , una factorización de un monoide libre es una secuencia de subconjuntos de palabras con la propiedad de que cada palabra del 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. ^{[ aclaración necesaria ]}

Sea A ^∗ el monoide libre de un alfabeto A . Sea X _i una secuencia de subconjuntos de A ^∗ indexados por un conjunto de índice totalmente ordenado I . Una factorización de una palabra w en A ^∗ es una expresión

${\displaystyle w=x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\ }$

con y . Algunos autores invierten el orden de las desigualdades. ${\displaystyle x_{i_{j}}\in X_{i_{j}}}$ ${\displaystyle i_{1}\geq i_{2}\geq \ldots \geq i_{n}}$

Teorema de Chen-Fox-Lyndon

Una palabra Lyndon sobre un alfabeto totalmente ordenado A es una palabra que es lexicográficamente menor 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 Lyndon. Por lo tanto, tomando X _l como el conjunto singleton { l } para cada palabra Lyndon l , con el conjunto de índices L de palabras Lyndon ordenadas lexicográficamente, obtenemos una factorización de A ^∗ . ^[2] Tal 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 :  list [ int ])  ->  list [ int ]: """Factorización monoide utilizando 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  mientras  i  <  n :  j ,  k  =  i  +  1 ,  i  mientras  j  <  n  y  s [ k ]  <=  s [ j ]:  si  s [ k ]  <  s [ j ]:  k  =  i  de lo contrario :  k  +=  1  j  +=  1  mientras  i  <=  k :  factorización . append ( s [ i : i  +  j  -  k ])  i  +=  j  -  k  devolver  factorización

Palabras del salón

El conjunto Hall proporciona una factorización. ^[5] De hecho, las palabras de Lyndon son un caso especial de palabras de Hall. El artículo sobre las palabras de Hall ofrece un esbozo de todos los mecanismos necesarios para establecer una prueba de esta factorización.

Bisección

Una bisección de un monoide libre es una factorización con solo dos clases X ₀ , X ₁ . ^[6]

Ejemplos:

A = { a , b }, X ₀ = { A ^∗ b }, X ₁ = { a }.

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]

${\displaystyle YX\cup A=X\cup Y\ .}$

En consecuencia, para cualquier partición P , Q de A ⁺ existe una bisección única ( X , Y ) con X un subconjunto de P e Y un subconjunto de Q. ^[8 ]

Teorema de Schützenberger

Este teorema establece que una secuencia X _i de subconjuntos de A ^∗ forma una factorización si y solo si se cumplen dos de las tres afirmaciones siguientes:

• Cada elemento de A ^∗ tiene al menos una expresión en la forma requerida; ^{[ aclaración necesaria ]}
• Cada elemento de A ^∗ tiene como máximo una expresión en la forma requerida;
• Cada clase conjugada C cumple sólo uno de los monoides M _i = X _i ^∗ y los elementos de C en M _i son conjugados en M _i . ^{[9] [ aclaración necesaria ]}

Véase también

• Sesquipoder

Referencias

1. Lothaire (1997) pág. 64
2. Lothaire (1997) pág. 67
3. 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..
4. "Factorización de Lyndon - Algoritmos para programación competitiva". cp-algorithms.com . Consultado el 30 de enero de 2024 .
5. Guy Melançon, (1992) "Combinatoria de árboles de Hall y palabras de Hall", Journal of Combinatoric Theory , 59A (2) págs. 285–308.
6. Lothaire (1997) pág. 68
7. Lothaire (1997) pág. 69
8. Lothaire (1997) pág. 71
9. Lothaire (1997) pág. 92

• Lothaire, M. (1997), Combinatoria de palabras , Enciclopedia de matemáticas y sus aplicaciones, vol. 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J.-É .; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, MP; Choffrut, C.; Cori, R.; Lyndon, R.; Rota, G.-C. Prólogo de Roger Lyndon (2.ª ed.), Cambridge University Press , ISBN 0-521-59924-5, Zbl  0874.20040