View source for Ehrenfeucht conjecture

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200501.png" /> be a finite alphabet. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200502.png" /> be the free [[Monoid|monoid]] generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200503.png" />. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200504.png" /> is called a language. At the beginning of the 1970s, A. Ehrenfeucht posed the following conjecture: For each language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200505.png" /> over a finite alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200506.png" /> there exists a finite subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200507.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200508.png" /> such that for any two morphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e1200509.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005010.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005011.png" /> the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005012.png" /> holds for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005013.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005014.png" /> if and only if it holds for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005015.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005016.png" />.

Such an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005017.png" /> is called a test set for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005018.png" />. In general, its existence is non-effective; however, it does exist effectively for every context-free language [[#References|[a1]]] (cf. also [[Grammar, context-free|Grammar, context-free]]).

The Ehrenfeucht conjecture can be restated as a compactness property of finitely generated free monoids. In order to present the generalized version, some terminology is needed. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005020.png" /> be two disjoint finite alphabets. A pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005021.png" /> is called an equation with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005022.png" /> as the set of variables. A system of equations is any set of equations. A solution (over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005023.png" />) of a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005024.png" /> is a [[Morphism|morphism]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005025.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005026.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005027.png" />. Finally, two systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005029.png" /> are equivalent (over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005030.png" />) if they have exactly the same solutions. Note that only systems of equations without constants are considered here. However, that, or the fact that the free monoid is finitely generated, is not essential.

The generalized Ehrenfeucht conjecture reads as follows: Each system of equations over a free monoid having a finite number of variables is equivalent to a finite subsystem of it.

The generalized form has been used independently in [[#References|[a2]]] and [[#References|[a5]]] to show that the Ehrenfeucht conjecture is a relatively straightforward consequence of the Hilbert basis theorem (cf. [[Hilbert theorem|Hilbert theorem]]). Both proofs use the fact that finitely generated monoids can be embedded into other algebraic structures, metabelian groups in [[#References|[a2]]] and rings of integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005031.png" />-matrices in [[#References|[a5]]]. Note that in the latter proof an algebraic structure with two operations, namely a [[Ring|ring]], is used to conclude a deep result on a structure with only one operation, namely on a monoid.

The compactness property expressed by the generalized Ehrenfeucht conjecture extends to other than free monoids, see [[#References|[a6]]] and [[#References|[a7]]]; the latter studies independent systems of equations over semi-groups.

The Ehrenfeucht conjecture originated in the work on the D<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005033.png" />L equivalence problem introduced by biologist A. Lindenmayer around 1970. ([[D0L-sequence|D0L]] stands for  "deterministic zero-interaction Lindenmayer" .) The problem asks for an algorithm to decide whether, for two endomorphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005035.png" /> on a finitely generated free monoid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005036.png" /> and for a word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005037.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005038.png" />, the equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005039.png" /> holds for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005040.png" />, i.e. whether the sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005042.png" /> coincide.

In biology the above sequences describe the development of filamentous organisms; the letters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005043.png" /> represent cells and the endomorphisms describe two sets of (non-interactive) developmental rules for cells. Thus, the problem is to decide whether two given sets of rules determine the same development of the organism. A positive direct solution of this difficult decision problem was given in [[#References|[a3]]].

In 1977, G.S. Makanin proved that it is decidable whether a given finite system of equations over a finitely generated free monoid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120050/e12005044.png" /> has a solution [[#References|[a9]]]. This deep result, together with the Ehrenfeucht conjecture, not only allows for a simpler proof of the decidability of the D0L equivalence problem, but also allows for a proof of the decidability of drastic generalizations of it, even those for which no direct proofs are known [[#References|[a4]]], [[#References|[a6]]]. A number of results concerning morphisms over free monoids which originated in the study of the D0L equivalence problem and the Ehrenfeucht conjecture are surveyed in [[#References|[a6]]], [[#References|[a8]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Albert,   K. Culik II,   J. Karhumäki,   "Test sets for context-free languages and algebraic systems of equations"  ''Inform. Control'' , '''52'''  (1982)  pp. 172–186</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.H. Albert,   J. Lawrence,   "A proof of Ehrenfeucht conjecture"  ''Theoret. Comput. Sci.'' , '''41'''  (1985)  pp. 121–123</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  K. Culik II,   I. Fris,   "The decidability of the equivalence problem for D0L systems"  ''Inform. Control'' , '''35'''  (1977)  pp. 20–39</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  K. Culik II,   J. Karhumäki,   "The equivalence problem for single-valued two-way transducers (on NPDT0L languages) is decidable"  ''SIAM J. Comput.'' , '''16'''  (1987)  pp. 221–230</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  V.S. Guba,   "The equivalence of infinite systems of equations in free groups and semigroups with finite subsystems"  ''Mat. Zametki'' , '''40'''  (1986)  pp. 321–324  (In Russian)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  T. Harju,   J. Karhumäki,   "Morphisms"  G. Rozenberg (ed.)  A. Salomaa (ed.) , ''Handbook of Formal Languages'' , '''1''' , Springer  (1997)  pp. 438–510</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  T. Harju,   J. Karhumäki,   W. Plandowski,   "Independent Systems of Equations"  J. Berstel (ed.)  D. Perrin (ed.) , ''Algebraic Combinatorics of Words''  (See: www-igm.univ-mlv.fr/~berstel/Lothaire/index.html)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J. Karhumäki,   "The impact of the D0L problem"  G. Rozenberg (ed.)  A. Salomaa (ed.) , ''Current Trends in Theoretical Computer Science, Essays and Tutorials'' , World Sci.  (1993)  pp. 586–594</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  G.S. Makanin,   "The problem of solvability of equations in a free semigroup"  ''Math. USSR Sb.'' , '''32'''  (1977)  pp. 129–198  ''Mat. Sb. (N.S.)'' , '''103'''  (1977)  pp. 147–236</TD></TR></table>