From Wikipedia, the free encyclopedia
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
- u = xw and wv = y
- 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", 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.|