Levi's lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The uw = x and v = wv case of 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

or

u = xw and wv = y

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]

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]

See also[edit]

Notes[edit]

  1. ^ 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)
  2. ^ Levi, F. W. (1944), "On semigroups", Bulletin of the Calcutta Mathematical Society 36: 141–146, MR 0011694, Zbl 0061.02405 .
  3. ^ Messner, J. (1997), "Pattern matching in trace monoids", Lecture Notes in Computer Science: 571–582, retrieved 2009-05-11