On the Ehrenfeucht conjecture for DOL languages. (English) Zbl 0544.68050

In this paper the Ehrenfeucht conjecture - that for every language \(L\subseteq \Sigma^*\) there exists a finite subset F of L such that for any pair of morphisms on \(\Sigma^*\), \(g(x)=h(x)\) for each x in L if and only if \(g(x)=h(x)\) for each x in F - is considered. Such a finite subset F has been called a test set for L. The notion of deviation of a string with respect to a language is introduced. Then this is used to give a sufficient condition for the existence of such a test set: ”Every language L over \(\{a_ 1,...,a_ t\}\) with bounded prefix deviation and fair distribution of letters has a test set.” Also it is proved that a test set effectively exists for each positive DOL language.
Reviewer: G.Orman


68Q45 Formal languages and automata
Full Text: EuDML


[1] 1. J. ALBERT, K. CULIK II and J. KARHUMAKI, Tests Sets for Context Free Languages and Systems of Equations Over a Free Monoid, Information and Control, Vol. 52, 1982, pp. 172-186. Zbl0522.68064 MR701592 · Zbl 0522.68064
[2] 2. K. CULIK II, The Ultimate Equivalence Problemfor DOL Systems, Acta Informatica, Vol. 10, 1978, pp. 79-84. Zbl0385.68060 MR495230 · Zbl 0385.68060
[3] 3. K. CULIK II, Homomorphisms: Decidability, Equality and Test Sets, in R. BOOK, Ed., Formal Language Theory, Perspectives and Open Problems, Academic Press, New York, 1980.
[4] 4. K. CULIK II, On the Decidability of the Séquence Equivalence Problem for DOL Systems, Theor. Comp. Science, Vol. 3, 1977, pp. 75-84. Zbl0352.68103 MR495228 · Zbl 0352.68103
[5] 5. K. CULIK II and J. KARHUMAKI, Systems of Equations Over a Free Monoid and Ehrenfeucht’s Conjecture, Discrete Mathematics, Vol. 43, 1983, pp. 139-153. Zbl0528.68057 MR685623 · Zbl 0528.68057
[6] 6. K. CULIK II and A. SALOMAA, On the Decidability of Homomorphism Equivalence for Languages, J. Comput. Systems Sc., Vol. 17, 1978, pp. 163-175. Zbl0389.68042 MR514269 · Zbl 0389.68042
[7] 7. K. CULIK II and A SALOMAA, Test Sets and Checking Words for Homomorphism Equivalence, J. Comput. Systems Sc., Vol. 21, 1980, pp. 379-395. Zbl0451.68046 MR584866 · Zbl 0451.68046
[8] 8. S. EILENBERG and M. P. SCHÜTZENBERGER, Rational Sets in Commutative Monoids, J. of Algebra, Vol. 13, 1969, pp. 173-191. Zbl0206.02703 MR246985 · Zbl 0206.02703
[9] 9. M. A. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading, Massachusetts, 1978. Zbl0411.68058 MR526397 · Zbl 0411.68058
[10] 10. J. KARHUMÄKI and I. SIMON, A Note on Elementary Homomorphisms and the Regularity of Equality Sets, EATCS Bulletin, Vol. 9, 1979, pp. 16-24.
[11] 11. M.KARPINSK, Ed., New Scottish Book of Problems, in preparation.
[12] 12. A. MANDEL and I. SIMON, On Finite Semigroups of Matrices, Theor. Comp. Science, Vol. 5, 1977, pp. 101-111. Zbl0368.20049 MR473070 · Zbl 0368.20049
[13] 13. G. ROZENBERG and A. SALOMAA, The Mathematical Theory of L Systems. Academic Press, New York, 1980. Zbl0508.68031 MR561711 · Zbl 0508.68031
[14] 14. A. SALOMAA and M. SOITTOLA, Automata-Theoretic Aspects of Formal Power Series, Springer Verlag, New York, 1978. Zbl0377.68039 MR483721 · Zbl 0377.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.