Levi's lemma

{{See Also|Word equation#Nielsen transformations}}

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.

{{citation

| last = Matiyasevich | first = Yu. V. | author-link = Yuri Matiyasevich

| title = A connection between systems of word and length equations and Hilbert's tenth problem

| journal = Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)

| pages = 132–144

| volume = 8

| year = 1968}}. A more general method for solving word equations is Makanin's algorithm.

{{citation

|last = Makanin | first = G. S. | author-link = Gennadii Semenovich Makanin

|title=The problem of solvability of equations in a free semigroup

|year=1977

|journal=Mat. Sbornik

|pages=147–236

|volume=103

| issue = 2 |others=English transl. in Math. USSR Sbornik 32 (1977)| bibcode = 1977SbMat..32..129M | doi = 10.1070/SM1977v032n02ABEH002376 }}

{{cite book

|author=M. Lothaire

|author-link = M. Lothaire

|title=Algebraic Combinatorics on Words

|chapter-url=https://archive.org/details/algebraiccombina0000loth

|chapter-url-access=registration

|year=2002

|publisher=Cambridge University Press

|isbn=0-521-81220-8

|chapter=12}}

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 originally due to Christine Duboc.

{{Citation

| title = On some equations in free partially commutative monoids

| year = 1986

| author = Duboc, Chr.

| journal = Theoretical Computer Science

| volume = 46

| pages = 159–174

| doi = 10.1016/0304-3975(86)90028-9

| doi-access = free

}}

Several proofs of Levi's Lemma for traces can be found in The Book of Traces.

{{cite book|editor1=Volker Diekert|editor2=Grzegorz Rozenberg|editor2-link=Grzegorz Rozenberg|title=The Book of Traces|year=1995|publisher=World Scientific|isbn=981-02-2058-8|pages=1–576}}

A monoid in which Levi's lemma holds is said to have the equidivisibility property.{{cite book|author1=Aldo de Luca|author2=Stefano Varricchio|title=Finiteness and Regularity in Semigroups and Formal Languages|year=1999|publisher=Springer Berlin Heidelberg|isbn=978-3-642-64150-3|page=2}} The free monoid 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 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. $f^\{-1\}(0)\; =\; \backslash \{1\_M\backslash \}$. (Note that f simply being a homomorphism does not guarantee this latter property, as there could be multiple elements of M mapped to 0.){{cite book|author=M. Lothaire|title=Combinatorics on Words|year=1997|publisher=Cambridge University Press|isbn=978-0-521-59924-5|page=13}} A monoid for which such a homomorphism exists is also called graded (and the f is called a gradation).{{citation | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=Cambridge University Press | year=2009 | isbn=978-0-521-84425-3 |page=26 }}

• String operations
• String functions (programming)

{{Reflist}}

Category:Combinatorics on words

Category:Lemmas