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 ]
Deje A * sea 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.
Teorema de Chen-Fox-Lyndon
Una palabra de Lyndon sobre un alfabeto A totalmente ordenado es una palabra 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 no creciente de palabras de Lyndon . Por tanto, tomando X l como el conjunto único { l } para cada palabra Lyndon l , con el conjunto índice L de palabras Lyndon ordenadas lexicográficamente, obtenemos una factorización de A * . [2] Tal factorización se puede encontrar en tiempo lineal. [3]
Palabras de pasillo
El conjunto Hall proporciona una factorización. [4] 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.
Bisección
Una bisección de un monoide libre es una factorización con solo dos clases X 0 , X 1 . [5]
Ejemplos:
- A = { a , b }, X 0 = { a * b }, X 1 = { 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 [6]
Como consecuencia, para cualquier partición P , Q de A + hay una bisección único ( X , Y ) con X un subconjunto de P y Y un subconjunto de Q . [7]
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 los siguientes tres enunciados:
- 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 C conjugada se encuentra con solo uno de los monoides M i = X i * y los elementos de C en M i se conjugan en M i . [8] [ aclaración necesaria ]
Ver también
Referencias
- ^ Lothaire (1997) p.64
- ^ Lothaire (1997) p.67
- ^ Duval, Jean-Pierre (1983). "Factorizar palabras sobre un alfabeto ordenado". Revista de algoritmos . 4 (4): 363–381. doi : 10.1016 / 0196-6774 (83) 90017-2 ..
- ^ Guy Melançon, (1992) " Combinatoria de árboles Hall y palabras Hall ", Diario de teoría combinatoria , 59A (2) págs. 285-308.
- ^ Lothaire (1997) p.68
- ^ Lothaire (1997) p.69
- ^ Lothaire (1997) p.71
- ↑ Lothaire (1997) p.92
- Lothaire, M. (1997), Combinatoria en palabras , Enciclopedia de las matemáticas y sus aplicaciones, 17 , Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, JE; Pirillo, G .; Foata, D .; Sakarovitch, J .; Simon, I .; Schützenberger, diputado; Choffrut, C .; Cori, R .; Lyndon, Roger; Rota, Gian-Carlo. Prólogo de Roger Lyndon (2.a ed.), Cambridge University Press , ISBN 0-521-59924-5, Zbl 0874.20040