Ehrenfeucht conjecture

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