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


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]


  1. ^ Mathematical Foundations of Computer Science 2004 Jiří Fiala, Václav Koubek, Jan Kratochvíl ISBN 3-540-22823-3, ISBN 978-3-540-22823-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