In theoretical computer science and mathematics, especially in the area of combinatorics on words, the Levi lemma states that, for all strings u, v, x and y, if uv = xy, then there exists a string w such that either
- uw = x and v = wy (if |u| ≤ |x|)
- u = xw and wv = y (if |u| ≥ |x|)
Levi's lemma can be applied repeatedly in order to solve word equations; in this context it is sometimes called the Nielsen transformation by analogy with the Nielsen transformation for groups. For example, starting with an equation xα = yβ where x and y are the unknowns, we can transform it (assuming |x| ≥ |y|, so there exists t such that x=yt) to ytα = yβ, thus to tα = β. This approach results in a graph of substitutions generated by repeatedly applying Levi's lemma. If each unknown appears at most twice, then word equation is called quadratic; in a quadratic word equation the graph obtained by repeatedly applying Levi's lemma is finite, so it is decidable if a quadratic word equation has a solution. (A more general method for solving word equations is Makanin's algorithm.)
A monoid in which Levi's lemma holds is said to have the equidivisibility property. The free monoid of strings and string concatenation has this property (by Levi's lemma for strings), but by itself equidivisibility is not enough to guarantee that a monoid is free. However an equidivisibile monoid M is free if additionally there exists a homomorphism f from M to the monoid of natural numbers (free monoid on one generator) with the property that the preimage of 0 contains only the identity element of M, i.e. . (Note that f simply being a homomorhism does not guarantee this latter property, as there could be multiple elements of M mapped to 0.) A monoid for which such a homorphims exists is also called graded (and the f is called a gradation).
- Elene Petre, "An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx" in Jiří Fiala, Václav Koubek, Jan Kratochvíl (eds.) Mathematical Foundations of Computer Science 2004, ISBN 978-3-540-22823-3, p. 810 (Lemma 3)
- Levi, F. W. (1944), "On semigroups", Bulletin of the Calcutta Mathematical Society, 36: 141–146, MR 0011694, Zbl 0061.02405.
- Messner, J. (1997), "Pattern matching in trace monoids" (PDF), Lecture Notes in Computer Science: 571–582, retrieved 2009-05-11
- Aldo de Luca; Stefano Varricchio (1999). Finiteness and Regularity in Semigroups and Formal Languages. Springer Berlin Heidelberg. p. 2. ISBN 978-3-642-64150-3.
- M. Lothaire (1997). Combinatorics on Words. Cambridge University Press. p. 13. ISBN 978-0-521-59924-5.
- Sakarovitch, Jacques (2009), Elements of automata theory, Translated from the French by Reuben Thomas, Cambridge: Cambridge University Press, p. 26, ISBN 978-0-521-84425-3