Systems of equations over a free monoid and Ehrenfeucht’s conjecture. (English) Zbl 0528.68057


68Q45 Formal languages and automata
20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
68Q42 Grammars and rewriting systems


Zbl 0454.20048
Full Text: DOI


[1] J. Albert, K. Culik II and J. Karhumaki, Test sets for context free languages and systems of equations over a free monoid, Inform. and Control, to appear. · Zbl 0477.68082
[2] Berstel, J., Transductions and context free languages, (1979), B.G. Teubner Stuttgart · Zbl 0424.68040
[3] Culik, K., Homomorphisms: decidability, equality and test sets, ()
[4] Culik, K.; Fris, I., The decidability of the equivalence problem for DOL systems, Inform. and control, 35, 20-39, (1977) · Zbl 0365.68074
[5] Culik, K.; Karhumaki, J., On the equality sets for homomorphisms on free monoids with two generators, R.A.I.R.O. theoretical informatics, 14, 349-369, (1980) · Zbl 0454.20048
[6] Culik, K.; Salomaa, A., On the decidability of homomorphism equivalence for languages, Jcss, 17, 163-175, (1978) · Zbl 0389.68042
[7] Culik, K.; Salomaa, A., Test sets and checking words for homorphism equivalence, Jcss, 379-395, (1980) · Zbl 0451.68046
[8] Ehrenfeucht, A.; Rozenberg, G., Simplication of homomorphisms, Inform. and control, 38, 289-309, (1978) · Zbl 0387.68062
[9] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[10] Karhumaki, J.; Simon, I., A note on elementary homomorphisms and the regularity of equality sets, EATCS bulletin, 9, 16-24, (1979)
[11] M. Karpinski, ed., New Scottish Book of Problems, in preparation.
[12] Linna, M., The decidability of the DOL prefix problem, Internat. J. of computer mathematics, 6, 127-142, (1977) · Zbl 0358.68114
[13] Makanin, G.S., The problem of solvability of equations in a free semigroup (in Russian), Matematiceskij sbornik, 103, 145, 148-236, (1977) · Zbl 0371.20047
[14] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072
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.