# Undecidability of infinite post correspondence problem for instances of size 8

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

- Volume: 46, Issue: 3, page 451-457
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topDong, Jing, and Liu, Qinghui. "Undecidability of infinite post correspondence problem for instances of size 8." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.3 (2012): 451-457. <http://eudml.org/doc/272993>.

@article{Dong2012,

abstract = {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.},

author = {Dong, Jing, Liu, Qinghui},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {ωPCP; semi-Thue system; undecidable; theory of computation; PCP; undecidability},

language = {eng},

number = {3},

pages = {451-457},

publisher = {EDP-Sciences},

title = {Undecidability of infinite post correspondence problem for instances of size 8},

url = {http://eudml.org/doc/272993},

volume = {46},

year = {2012},

}

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

PB - EDP-Sciences

VL - 46

IS - 3

SP - 451

EP - 457

AB - 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.

LA - eng

KW - ωPCP; semi-Thue system; undecidable; theory of computation; PCP; undecidability

UR - http://eudml.org/doc/272993

ER -

## References

top- [1] V.D. Blondel and V. Canterini, Undecidable problems for probabilistic automata of fixed dimension. Theor. Comput. Syst.36 (2003) 231–245. Zbl1039.68061MR1962327
- [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. Zbl0493.68076MR677104
- [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. Zbl1114.03035MR2277048
- [4] V. Halava, T. Harju and M. Hirvensalo, Binary (generalized) Post Correspondence Problem. Theoret. Comput. Sci.276 (2002) 183–204. Zbl1023.03038MR1896352
- [5] Y. Matiyasevich and G. Sénizergues, Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci.330 (2005) 145–169. Zbl1078.03033MR2112772
- [6] E. Post, A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc.52 (1946) 264–268. Zbl0063.06329MR15343
- [7] K. Ruohonen, Reversible machines and Posts Correspondence Problem for biprefix morphisms. J. Inform. Process. Cybernet.EIK21 (1985) 579–595. Zbl0604.68057MR825861