# Levi's lemma

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*|)

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.^{[1]} Levi's lemma is named after Friedrich Wilhelm Levi, who published it in 1944.^{[2]}

## 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.^{[1]} (A more general method for solving word equations is Makanin's algorithm.)^{[1]}

## 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.^{[3]}

A monoid in which Levi's lemma holds is said to have the **equidivisibility property**.^{[4]} 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.)^{[5]} A monoid for which such a homorphims exists is also called *graded* (and the *f* is called a gradation).^{[6]}

## See also

## Notes

- 1 2 3 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