En informática teórica y matemáticas , especialmente en el área de 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
o
Es decir, hay una cadena w que está "en el medio", y puede agruparse hacia un lado o hacia el otro. El lema de Levi recibe su 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 lo llama 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 (asumiendo |x| ≥ |y| , por lo que existe t tal que x = yt ) en ytα = yβ , por lo tanto en 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 de palabras 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 palabras 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 aparecer en una forma más general en la teoría de grafos y en la teoría de monoides ; por ejemplo, existe un lema de Levi más general para trazas originalmente debido a Christine Duboc. [5] Varias pruebas del lema de Levi para trazas se pueden encontrar en El libro de las trazas . [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 (por el lema de Levi para cadenas), pero por sí misma la equidivisibilidad no es suficiente para garantizar que un monoide sea libre. Sin embargo, un monoide equidivisible 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 identidad de M , es decir . (Obsérvese que el simple hecho de que f sea un homomorfismo no garantiza esta última propiedad, ya que podría haber múltiples elementos de M mapeados a 0). [8] Un monoide para el que existe tal homomorfismo también se denomina graduado (y la f se denomina gradación). [9]
