En la informática teórica y las matemáticas , especialmente en el área de la combinatoria de palabras , el Levi lema establece que, para todas las cadenas u , v , x e Y , si uv = xy , entonces existe una cadena w tal que sea
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/8/88/Levi%27s_lemma.svg/400px-Levi%27s_lemma.svg.png)
- uw = x y v = wy (si | u | ≤ | x |)
o
- u = xw y wv = y (si | u | ≥ | x |)
Es decir, hay una cadena w que está "en el medio" y se puede agrupar a un lado o al otro. El lema de Levi lleva el nombre de Friedrich Wilhelm Levi , quien lo publicó en 1944. [1]
Aplicaciones
El lema de Levi se puede aplicar repetidamente para resolver ecuaciones de palabras ; en este contexto, a veces se denomina transformación de Nielsen por analogía con la transformación de Nielsen para grupos . Por ejemplo, a partir de una ecuación xα = yβ donde x y y son las incógnitas, podemos transformarlo (suponiendo | x | ≥ | y | , por lo que no existe t tal que x = yt ) para ytα = yβ , para así tα = β . Este enfoque da como resultado un gráfico de sustituciones generado al aplicar repetidamente el lema de Levi. Si cada incógnita aparece como máximo dos veces, entonces una ecuación de palabras se llama cuadrática; en una ecuación cuadrática de palabras, la gráfica obtenida al aplicar repetidamente el lema de Levi es finita, por lo que es decidible si una ecuación cuadrática de palabras tiene una solución . [2] Un método más general para resolver ecuaciones de palabras es el algoritmo de Makanin . [3] [4]
Generalizaciones
Lo anterior se conoce como el lema de Levi para cuerdas ; el lema puede aparecer de forma más general en la teoría de grafos y en la teoría de monoides ; por ejemplo, hay un lema de Levi más general para los rastros originalmente debidos a Christine Duboc. [5] Varias pruebas del Lema de Levi para las huellas se pueden encontrar en El libro de las huellas . [6]
Se dice que un monoide en el que se mantiene el lema de Levi tiene la propiedad de equidivisibilidad . [7] El monoide libre de cadenas y la concatenación de cadenas tiene esta propiedad (según el lema de Levi para cadenas), pero la equidivisibilidad en sí misma no es suficiente para garantizar que un monoide sea libre. Sin embargo, un monoide equidivisibile M es libre si además existe un homomorfismo f de M al monoide de números naturales (monoide libre en un generador) con la propiedad de que la preimagen de 0 contiene solo el elemento de identidad de M , es decir. (Tenga en cuenta que f simplemente ser un homomorfismo no garantiza esta última propiedad, ya que podría haber múltiples elementos de M asignados a 0). [8] Un monoide para el cual existe tal homomorfismo también se llama graduado (y la f se llama un gradación). [9]
Ver también
Notas
- ^ Levi, FW (1944), "Sobre semigrupos", Boletín de la Sociedad Matemática de Calcuta , 36 : 141-146, MR 0011694 , Zbl 0061.02405 .
- ^ Matiyasevich, Yu. V. (1968), "Una conexión entre sistemas de ecuaciones de palabra y longitud y el décimo problema de Hilbert", Zap. Naučn. Sem. Leningrado. Otdel. Estera. Inst. Steklov. (LOMI) , 8 : 132-144.
- ^ Makanin, GS (1977), traducción al inglés. en matemáticas. URSS Sbornik 32 (1977), "El problema de la resolución de ecuaciones en un semigrupo libre", Mat. Sbornik , 103 (2): 147–236, Bibcode : 1977SbMat..32..129M , doi : 10.1070 / SM1977v032n02ABEH002376
- ^ M. Lothaire (2002). "12" . Combinatoria algebraica de palabras . Prensa de la Universidad de Cambridge. ISBN 0-521-81220-8.
- ^ Duboc, Chr. (1986), "Sobre algunas ecuaciones en monoides parcialmente conmutativos libres", Theoretical Computer Science , 46 : 159-174, doi : 10.1016 / 0304-3975 (86) 90028-9
- ^ Volker Diekert; Grzegorz Rozenberg , eds. (1995). El libro de las huellas . World Scientific. págs. 1-576. ISBN 981-02-2058-8.
- ^ Aldo de Luca; Stefano Varricchio (1999). Finitud y regularidad en semigrupos y lenguajes formales . Springer Berlín Heidelberg. pag. 2. ISBN 978-3-642-64150-3.
- ^ M. Lothaire (1997). Combinatoria en palabras . Prensa de la Universidad de Cambridge. pag. 13. ISBN 978-0-521-59924-5.
- ^ Sakarovitch, Jacques (2009), Elementos de la teoría de los autómatas , traducido del francés por Reuben Thomas, Cambridge: Cambridge University Press , p. 26, ISBN 978-0-521-84425-3