Namespaces
Variants
Actions

Difference between revisions of "Ehrenfeucht conjecture"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 43 formulas out of 43 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
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" />.
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
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]]).
+
Out of 43 formulas, 43 were replaced by TEX code.-->
  
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.
+
{{TEX|semi-auto}}{{TEX|done}}
 +
Let $\Sigma$ be a finite alphabet. Let $\Sigma ^ { * }$ be the free [[Monoid|monoid]] generated by $\Sigma$. A subset $L \subseteq \Sigma ^ { * }$ is called a language. At the beginning of the 1970s, A. Ehrenfeucht posed the following conjecture: For each language $L$ over a finite alphabet $\Sigma$ there exists a finite subset $F$ of $L$ such that for any two morphisms $g$ and $h$ on $\Sigma ^ { * }$ the equation $g ( x ) = h ( x )$ holds for all $x$ in $L$ if and only if it holds for all $x$ in $F$.
 +
 
 +
Such an $F$ is called a test set for $L$. 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 $\Sigma$ and $\Omega$ be two disjoint finite alphabets. A pair $( u , v ) \in \Omega ^ { * } \times \Omega ^ { * }$ is called an equation with $\Omega$ as the set of variables. A system of equations is any set of equations. A solution (over $\Sigma ^ { * }$) of a system $S$ is a [[Morphism|morphism]] $h : \Omega ^ { * } \rightarrow \Sigma ^ { * }$ such that $h ( u ) = h ( v )$ for all $( u = v ) \in S$. Finally, two systems $S _ { 1 }$ and $S _ { 2 }$ are equivalent (over $\Sigma ^ { * }$) 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 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 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 $( 2 \times 2 )$-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 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 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.
+
The Ehrenfeucht conjecture originated in the work on the D$0$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 $h$ and $g$ on a finitely generated free monoid $\Sigma ^ { * }$ and for a word $w$ in $\Sigma ^ { * }$, the equality $h ^ { i } ( w ) = g ^ { i } ( w )$ holds for all $i \geq 0$, i.e. whether the sequences $w, h ( w ) , h ^ { 2 } ( w ),\dots$ and $w , g ( w ) , g ^ { 2 } ( w ), \dots$ 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 biology the above sequences describe the development of filamentous organisms; the letters of $\Sigma$ 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]]].
+
In 1977, G.S. Makanin proved that it is decidable whether a given finite system of equations over a finitely generated free monoid $\Sigma ^ { * }$ 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====
 
====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>
+
<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>

Latest revision as of 16:57, 1 July 2020

Let $\Sigma$ be a finite alphabet. Let $\Sigma ^ { * }$ be the free monoid generated by $\Sigma$. A subset $L \subseteq \Sigma ^ { * }$ is called a language. At the beginning of the 1970s, A. Ehrenfeucht posed the following conjecture: For each language $L$ over a finite alphabet $\Sigma$ there exists a finite subset $F$ of $L$ such that for any two morphisms $g$ and $h$ on $\Sigma ^ { * }$ the equation $g ( x ) = h ( x )$ holds for all $x$ in $L$ if and only if it holds for all $x$ in $F$.

Such an $F$ is called a test set for $L$. In general, its existence is non-effective; however, it does exist effectively for every context-free language [a1] (cf. also 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 $\Sigma$ and $\Omega$ be two disjoint finite alphabets. A pair $( u , v ) \in \Omega ^ { * } \times \Omega ^ { * }$ is called an equation with $\Omega$ as the set of variables. A system of equations is any set of equations. A solution (over $\Sigma ^ { * }$) of a system $S$ is a morphism $h : \Omega ^ { * } \rightarrow \Sigma ^ { * }$ such that $h ( u ) = h ( v )$ for all $( u = v ) \in S$. Finally, two systems $S _ { 1 }$ and $S _ { 2 }$ are equivalent (over $\Sigma ^ { * }$) 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 [a2] and [a5] to show that the Ehrenfeucht conjecture is a relatively straightforward consequence of the Hilbert basis theorem (cf. Hilbert theorem). Both proofs use the fact that finitely generated monoids can be embedded into other algebraic structures, metabelian groups in [a2] and rings of integer $( 2 \times 2 )$-matrices in [a5]. Note that in the latter proof an algebraic structure with two operations, namely a 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 [a6] and [a7]; the latter studies independent systems of equations over semi-groups.

The Ehrenfeucht conjecture originated in the work on the D$0$L equivalence problem introduced by biologist A. Lindenmayer around 1970. (D0L stands for "deterministic zero-interaction Lindenmayer" .) The problem asks for an algorithm to decide whether, for two endomorphisms $h$ and $g$ on a finitely generated free monoid $\Sigma ^ { * }$ and for a word $w$ in $\Sigma ^ { * }$, the equality $h ^ { i } ( w ) = g ^ { i } ( w )$ holds for all $i \geq 0$, i.e. whether the sequences $w, h ( w ) , h ^ { 2 } ( w ),\dots$ and $w , g ( w ) , g ^ { 2 } ( w ), \dots$ coincide.

In biology the above sequences describe the development of filamentous organisms; the letters of $\Sigma$ 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 [a3].

In 1977, G.S. Makanin proved that it is decidable whether a given finite system of equations over a finitely generated free monoid $\Sigma ^ { * }$ has a solution [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 [a4], [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 [a6], [a8].

References

[a1] 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
[a2] M.H. Albert, J. Lawrence, "A proof of Ehrenfeucht conjecture" Theoret. Comput. Sci. , 41 (1985) pp. 121–123
[a3] K. Culik II, I. Fris, "The decidability of the equivalence problem for D0L systems" Inform. Control , 35 (1977) pp. 20–39
[a4] 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
[a5] 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)
[a6] T. Harju, J. Karhumäki, "Morphisms" G. Rozenberg (ed.) A. Salomaa (ed.) , Handbook of Formal Languages , 1 , Springer (1997) pp. 438–510
[a7] 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)
[a8] 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
[a9] 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
How to Cite This Entry:
Ehrenfeucht conjecture. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ehrenfeucht_conjecture&oldid=13042
This article was adapted from an original article by K. Culik II (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article