×
Halava, Vesa; Harju, Tero; Hirvensalo, Mika

Binary (generalized) Post Correspondence Problem. (English) Zbl 1023.03038

Theor. Comput. Sci. 276, No. 1-2, 183-204 (2002).
We give a new proof for the decidability of the binary Post Correspondence Problem (PCP) originally proved in 1982 by A. Ehrenfeucht, J. Karhumäki and G. Rozenberg [Theor. Comput. Sci. 21, 119-144 (1982; Zbl 0493.68076)]. Our proof is complete and somewhat shorter than the original proof although we use the same basic idea.

Cited in 9 Documents

MSC:

03D40 Word problems, etc. in computability and recursion theory
03B25 Decidability of theories and sets of sentences
68Q45 Formal languages and automata

Keywords:

binary Post Correspondence Problem; generalised Post Correspondence Problem; marked morphisms; decidability

Citations:

Zbl 0493.68076
PDF BibTeX XML Cite
\textit{V. Halava} et al., Theor. Comput. Sci. 276, No. 1--2, 183--204 (2002; Zbl 1023.03038)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[2] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., The (generalized) post correspondence problem with lists consisting of two words is decidable, Theoret. comput. sci., 21, 2, 119-144, (1982) · Zbl 0493.68076
[3] Halava, V.; Harju, T.; Hirvensalo, M., Generalized post correspondence problem for marked morphisms, Internat. J. algebra comput., 10, 6, 757-772, (2000) · Zbl 0971.68124
[4] Halava, V.; Hirvensalo, M.; de Wolf, R., Marked PCP is decidable, Theoret. comput. sci., 255, 1-2, 193-204, (2001) · Zbl 0974.68097
[5] Harju, T.; Karhumäki, J., Morphisms, (), 439-510
[6] T. Harju, J. Karhumäki, D. Krob, Remarks on Generalized Post Correspondence Problem, Lecture Notes in Computer Science, vol. 1046, Springer, Berlin, 1996, pp. 39-48. · Zbl 1379.03009
[7] Y. Matiyasevich, G. Sénizergues, Decision problems for semi-Thue systems with a few rules, Proc. 11th IEEE Symp. on Logic in Computer Science, 1996, pp. 523-531.
[8] Post, E.L., A variant of a recursively unsolvable problem, Bull. amer. math. soc., 52, 264-268, (1946) · Zbl 0063.06329
[9] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
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.