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
Contents
uw = x and v = wy (if |u| ≤ |x|)or
u = xw and wv = y (if |u| ≥ |x|)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 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.
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.