The (generalized) Post correspondence problem with lists consisting of two words is decidable. (English) Zbl 0493.68076


68Q45 Formal languages and automata
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20M05 Free semigroups, generators and relations, word problems
03D40 Word problems, etc. in computability and recursion theory
20M35 Semigroups in automata theory, linguistics, etc.


Zbl 0485.03018
Full Text: DOI


[1] Book, R.V.; Brandenburg, F.J., Equality sets and complexity classes, SIAM J. comput., 9, 729-743, (1980) · Zbl 0446.68040
[2] Culik, K., A purely homomorphic characterization of recursively enumerable sets, J. ACM, 26, 345-350, (1979) · Zbl 0395.68076
[3] Claus, V., Die grenze zwischen entscheidbarkeit und nichtentscheidbarkeit, (1979), Fernstudienkurs für die Fernuniversität Hagen, Open University Hagen
[4] Culik, K.; Karhumäki, J., On the equality sets for homomorphisms on free monoids with two generators, R.A.I.R.O., informatique théorique, 14, 349-369, (1980) · Zbl 0454.20048
[5] Engelfriet, J.; Rozenberg, G., Fixed point languages, equality languages and representations of recursively enumerable languages, J. ACM, 27, 499-518, (1980) · Zbl 0475.68047
[6] Ehrenfeucht, A.; Rozenberg, G., Generalized post correspondence problem of length 2, () · Zbl 0482.68073
[7] Ginsburg, S., The mathematical theory of context-free languages, (1966), McGraw-Hill New York · Zbl 0184.28401
[8] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[9] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[10] Karhumäki, J.; Simon, I., A note on elementary homomorphisms and the regularity of equality sets, Bull. EATCS, 9, (1979)
[11] Lecerf, Y., Recursive insolubilité de l’equation generale de diagonalisation de deux monomorphisms de monoides libres φx = ψx, C.R. acad. sci. Paris, 257, 2940-2943, (1963) · Zbl 0192.06902
[12] Post, E.L., A variant of a recursively unsolvable problem, Bull. amer. math. soc., 52, 264-268, (1946) · Zbl 0063.06329
[13] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
[14] Salomaa, A., Equality sets for homomorphisms on free monoids, Acta cybernet., 4, 127-239, (1978) · Zbl 0407.68077
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.