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 or That is, there is a string w that is "in the middle", and can be grouped to one side or the other. Levi's lemma is named after Friedrich Wilhelm Levi, who published it in 1944.

Applications

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 a 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.

Generalizations

The above is known as the Levi lemma for strings; the lemma can occur in a more general form in graph theory and in monoid theory; for example, there is a more general Levi lemma for traces originally due to Christine Duboc. Several proofs of Levi's Lemma for traces can be found in The Book of Traces. 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 equidivisible 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 homomorphism does not guarantee this latter property, as there could be multiple elements of M mapped to 0.) A monoid for which such a homomorphism exists is also called graded (and the f is called a gradation).