Undecidability of infinite post correspondence problem for instances of size 8
Dong, Jing ; Liu, Qinghui
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012), p. 451-457 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231-245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO-Theor. Inf. Appl. 40 (2006) 551-557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju's construction. So we prove that ωPCP is undecidable for domain alphabets of size 8.

Publié le : 2012-01-01
DOI : https://doi.org/10.1051/ita/2012015
Classification:  03D35,  03D40,  68R15 
@article{ITA_2012__46_3_451_0,
     author = {Dong, Jing and Liu, Qinghui},
     title = {Undecidability of infinite post correspondence problem for instances of size 8},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {46},
     year = {2012},
     pages = {451-457},
     doi = {10.1051/ita/2012015},
     mrnumber = {2981678},
     zbl = {1257.03069},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2012__46_3_451_0}
}

Dong, Jing; Liu, Qinghui. Undecidability of infinite post correspondence problem for instances of size 8. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 451-457. doi : 10.1051/ita/2012015. http://gdmltest.u-ga.fr/item/ITA_2012__46_3_451_0/

[1] V.D. Blondel and V. Canterini, Undecidable problems for probabilistic automata of fixed dimension. Theor. Comput. Syst. 36 (2003) 231-245. | MR 1962327 | Zbl 1039.68061

[2] 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. | MR 677104 | Zbl 0493.68076

[3] V. Halava and T. Harju, Undecibability of infinite Post Correspondence Problem for instances of size 9. RAIRO-Theor. Inf. Appl. 40 (2006) 551-557. | Numdam | MR 2277048 | Zbl 1114.03035

[4] V. Halava, T. Harju and M. Hirvensalo, Binary (generalized) Post Correspondence Problem. Theoret. Comput. Sci. 276 (2002) 183-204. | MR 1896352 | Zbl 1023.03038

[5] Y. Matiyasevich and G. Sénizergues, Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci. 330 (2005) 145-169. | MR 2112772 | Zbl 1078.03033

[6] E. Post, A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946) 264-268. | MR 15343 | Zbl 0063.06329

[7] K. Ruohonen, Reversible machines and Posts Correspondence Problem for biprefix morphisms. J. Inform. Process. Cybernet.EIK 21 (1985) 579-595. | MR 825861 | Zbl 0604.68057