In
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
and
mathematics, especially in the area of
combinatorics on words
Combinatorics on words is a fairly new field of mathematics, branching from combinatorics, which focuses on the study of words and formal languages. The subject looks at letters or symbols, and the sequences they form. Combinatorics on words af ...
, the Levi lemma states that, for all
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
''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'', )
or
:''u'' = ''xw'' and ''wv'' = ''y'' (if , ''u'', ≥ , ''x'', )
That is, there is a string ''w'' that is "in the middle", and can be grouped to one side or the other. Levi's lemma is named after
Friedrich Wilhelm Levi
Friedrich Wilhelm Daniel Levi (February 6, 1888 – January 1, 1966) was a German mathematician known for his work in abstract algebra, especially torsion-free abelian groups. He also worked in geometry, topology, set theory, and analysis.
Early ...
, who published it in 1944.
Applications
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 a 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.
[
][
]
Generalizations
The above is known as the Levi lemma for strings; the lemma can occur in a more general form in
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
and in
monoid theory
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy ...
; for example, there is a more general Levi lemma for
traces
Traces may refer to:
Literature
* ''Traces'' (book), a 1998 short-story collection by Stephen Baxter
* ''Traces'' series, a series of novels by Malcolm Rose
Music Albums
* ''Traces'' (Classics IV album) or the title song (see below), 1969
* ''Tra ...
originally due to Christine Duboc.
[
]
Several proofs of Levi's Lemma for traces can be found in ''The Book of Traces''.
[
]
A monoid in which Levi's lemma holds is said to have the equidivisibility property.
The
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
of strings and string concatenation has this property (by Levi's lemma for strings), but by itself equidivisibility is not enough to guarantee that a monoid is free. However an equidivisible monoid ''M'' is free if additionally there exists a
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
''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 homomorphism does not guarantee this latter property, as there could be multiple elements of ''M'' mapped to 0.)
A monoid for which such a homomorphism exists is also called ''graded'' (and the ''f'' is called a gradation).
See also
*
String operations In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical ...
*
String functions (programming)
Notes
{{Reflist
Combinatorics on words
Lemmas