×
Halava, Vesa; Harju, Tero; Karhumäki, Juhani

Decidability of the binary infinite Post Correspondence Problem. (English) Zbl 1023.03039

Discrete Appl. Math. 130, No. 3, 521-526 (2003).
Summary: We show that it is decidable for binary instances of the Post Correspondence Problem whether the instance has an infinite solution. In this context, a binary instance (\(h,g\)) consists of two morphisms \(h\) and \(g\) with a common two-element domain alphabet. An infinite solution is an infinite word \(\omega =a_1a_2...\) such that \(h(\omega)=g(\omega)\). This problem is known to be undecidable for the unrestricted instances of the Post Correspondence Problem.

Cited in 1 Review
Cited in 2 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; infinite solutions; decidability; binary instance; infinite word
PDF BibTeX XML Cite
\textit{V. Halava} et al., Discrete Appl. Math. 130, No. 3, 521--526 (2003; Zbl 1023.03039)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., The (generalized) post correspondence problem with lists consisting of two words is decidable, Theoret. comput. sci., 21, 119-144, (1982) · Zbl 0493.68076
[2] V. Halava, Post correspondence problem and its modifications for marked morphisms, Ph.D. Thesis, TUCS Dissertations, Vol. 37, University of Turku, 2002.
[3] Halava, V.; Harju, T., Infinite solutions of the marked post correspondence problem, (), 57-68 · Zbl 1060.03068
[4] Halava, V.; Harju, T.; Hirvensalo, M., Binary (generalized) post correspondence problem, Theoret. comput. sci., 276, 1-2, 183-204, (2002) · Zbl 1023.03038
[5] Halava, V.; Hirvensalo, M.; de Wolf, R., Marked PCP is decidable, Theoret. comput. sci., 255, 1-2, 193-204, (2001) · Zbl 0974.68097
[6] Holub, Š., Binary equality sets are generated by two words, Internat. J. algebra, 259, 1-42, (2003) · Zbl 1010.68101
[7] Š. Holub, A unique structure of two-generated binary equality languages, in: M. Ito, M. Toyama (Eds.), Developments in Language Theory, DLT 2002, Lecture Notes in Computer Science 2450, Springer, Berlin, 2003. · Zbl 1015.68089
[8] Y. Matiyasevich, G. Sénizergues, Decision problems for semi-Thue systems with a few rules, in: Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science, New Brunswick, NJ, 27-30 July 1996, IEEE Computer Society, Silver Spring, MD, pp. 523-531.
[9] Post, E., A variant of a recursively unsolvable problem, Bull. amer. math. soc., 52, 264-268, (1946) · Zbl 0063.06329
[10] Ruohonen, K., Reversible machines and Post’s correspondence problem for biprefix morphisms, Elektron. inform. kybernet. (EIK), 21, 12, 579-595, (1985) · Zbl 0604.68057
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.