Lema de Levi
En informática y matemáticas teóricas , especialmente en el área de la combinatoria de palabras , el lema de Levi establece que, para todas las cadenas u , v , x e y , si uv = xy , entonces existe una cadena w tal que
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]
El lema de Levi se puede aplicar repetidamente para resolver ecuaciones de palabras ; en este contexto, a veces se la denomina transformación de Nielsen por analogía con la transformación de Nielsen para grupos . Por ejemplo, comenzando con una ecuación xα = yβ donde x e y son las incógnitas, podemos transformarla (suponiendo que |x| ≥ |y| , entonces existe t tal que x = yt ) a ytα = yβ , por lo tanto a 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 en palabras se llama cuadrática; en una ecuación de palabra cuadrática, el gráfico obtenido al aplicar repetidamente el lema de Levi es finito, por lo que es decidible si una ecuación de palabra cuadrática tiene una solución . [2] Un método más general para resolver ecuaciones de palabras es el algoritmo de Makanin . [3] [4]
Lo anterior se conoce como el lema de Levi para cuerdas ; el lema puede ocurrir en una forma más general en la teoría de grafos y en la teoría monoide ; por ejemplo, hay un lema de Levi más general para las huellas originalmente debido a Christine Duboc. [5] Varias demostraciones del Lema de Levi para huellas se pueden encontrar en El Libro de las Huellas . [6]
Se dice que un monoide en el que se cumple 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 por 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 los 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 fel simple hecho de 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 que existe tal homomorfismo también se denomina graduado (y la f se denomina gradación). [9]
