Geodesic
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

Voir la notice de l'article provenant de la source Numdam

MR Zbl EuDML

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
Keywords: ωPCP, semi-Thue system, undecidable, theory of computation 
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
@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},
     year = {2012},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {3},
     doi = {10.1051/ita/2012015},
     mrnumber = {2981678},
     zbl = {1257.03069},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/articles/10.1051/ita/2012015/
%R 10.1051/ita/2012015
%G en
%F ITA_2012__46_3_451_0

Cité par Sources :