Levi's lemma

In theoretical computer science and mathematics, especially in the area of combinatorics, 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]

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.^[2]

See also

• String operations
• String functions (programming)
• Transfinite strings

Notes