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 : 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},
     mrnumber = {2981678},
     zbl = {1257.03069},
     language = {en},
     url = {http://archive.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
SP  - 451
EP  - 457
VL  - 46
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2012015/
DO  - 10.1051/ita/2012015
LA  - en
ID  - ITA_2012__46_3_451_0
ER  - 
%0 Journal Article
%A Dong, Jing
%A Liu, Qinghui
%T Undecidability of infinite post correspondence problem for instances of size 8
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2012
%P 451-457
%V 46
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2012015/
%R 10.1051/ita/2012015
%G en
%F 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) no. 3, pp. 451-457. doi : 10.1051/ita/2012015. http://archive.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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

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

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

Cité par Sources :