×

Undecidability of infinite Post correspondence problem for instances of size 9. (English) Zbl 1114.03035

The authors prove a strong improvement of V. D. Blondel and V. Canterini’s theorem [Theory Comput. Syst. 36, No. 3, 231–245 (2003; Zbl 1039.68061)]: the infinite Post correspondence problem is undecidable for morphisms of size 9 (Blondel and Canterini proved undecidability for size 105). It is not known whether the problem is undecidable for morphisms of size between 3 and 8.

MSC:

03D35 Undecidability and degrees of sets of sentences
03D40 Word problems, etc. in computability and recursion theory
68R15 Combinatorics on words

Citations:

Zbl 1039.68061
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML Link

References:

[1] V.D. Blondel and V. Canterini , Undecidable problems for probabilistic automata of fixed dimension . Theory Comput. Syst. 36 ( 2003 ) 231 - 245 . Zbl 1039.68061 · Zbl 1039.68061
[2] V. Claus , Some remarks on PCP(k) and related problems . Bull. EATCS 12 ( 1980 ) 54 - 61 .
[3] A. Ehrenfeucht , J. Karhumäki and G. Rozenberg , The (generalized) Post Correspondence Problem with lists consisting of two words is decidable . Theoret. Comput. Sci. 21 ( 1982 ) 119 - 144 . Zbl 0493.68076 · Zbl 0493.68076
[4] V. Halava and T. Harju , Infinite solutions of the marked Post Correspondence Problem , in Formal and Natural Computing, edited by J. Karhumäki, W. Brauer, H. Ehrig and A. Salomaa. Lecture Notes in Comput. Sci. 2300 ( 2002 ) 57 - 68 . Zbl 1060.03068 · Zbl 1060.03068
[5] V. Halava , T. Harju and M. Hirvensalo , Binary (generalized) Post Correspondence Problem . Theoret. Comput. Sci. 276 ( 2002 ) 183 - 204 . Zbl 1023.03038 · Zbl 1023.03038
[6] V. Halava , T. Harju and J. Karhumäki , Decidability of the binary infinite Post Correspondence Problem . Discrete Appl. Math. 130 ( 2003 ) 521 - 526 . Zbl 1023.03039 · Zbl 1023.03039
[7] T. Harju and J. Karhumäki , Morphisms , in Handbook of Formal Languages, volume 1, edited by G. Rozenberg and A. Salomaa, Springer-Verlag ( 1997 ) 439 - 510 .
[8] T. Harju , J. Karhumäki and D. Krob , Remarks on generalized Post correspondence problem , in STACS’96, edited by C. Puech and R. Reischuk. Lect. Notes Comput. Sci. 1046 ( 1996 ) 39 - 48 . · Zbl 1379.03009
[9] Y. Matiyasevich and G. Sénizergues , Decision problems for semi-Thue systems with a few rules . Theor. Comput. Sci. 330 ( 2005 ) 145 - 169 . Zbl 1078.03033 · Zbl 1078.03033
[10] E. Post , A variant of a recursively unsolvable problem . Bull. Amer. Math. Soc. 52 ( 1946 ) 264 - 268 . Article | Zbl 0063.06329 · Zbl 0063.06329
[11] K. Ruohonen , Reversible machines and Post’s correspondence problem for biprefix morphisms . J. Inform. Process. Cybernet. EIK 21 ( 1985 ) 579 - 595 . Zbl 0604.68057 · 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.