Undecidability of infinite post correspondence problem for instances of size 8
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 3, pp. 451-457.

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.

DOI : https://doi.org/10.1051/ita/2012015
Classification : 03D35,  03D40,  68R15
Mots clés : ωPCP, semi-Thue system, undecidable, theory of computation
@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},
     pages = {451--457},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {3},
     year = {2012},
     doi = {10.1051/ita/2012015},
     zbl = {1257.03069},
     mrnumber = {2981678},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2012015/}
}
TY  - JOUR
AU  - Dong, Jing
AU  - Liu, Qinghui
TI  - Undecidability of infinite post correspondence problem for instances of size 8
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2012
DA  - 2012///
SP  - 451
EP  - 457
VL  - 46
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2012015/
UR  - https://zbmath.org/?q=an%3A1257.03069
UR  - https://www.ams.org/mathscinet-getitem?mr=2981678
UR  - https://doi.org/10.1051/ita/2012015
DO  - 10.1051/ita/2012015
LA  - en
ID  - ITA_2012__46_3_451_0
ER  - 
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) no. 3, pp. 451-457. doi : 10.1051/ita/2012015. http://www.numdam.org/articles/10.1051/ita/2012015/

[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

Cité par Sources :