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|)
More generally, a monoid in which Levi's lemma holds is said to have the equidivisibility property. The free monoid obviously has this property, 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).
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.)
- 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.
- 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
- Messner, J. (1997), "Pattern matching in trace monoids" (PDF), Lecture Notes in Computer Science: 571–582, retrieved 2009-05-11
|This combinatorics-related article is a stub. You can help Wikipedia by expanding it.|