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

RAIRO - Theoretical Informatics and 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 46.3 (2012): 451-457. <http://eudml.org/doc/222079>.

@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},

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

language = {eng},

month = {8},

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/222079},

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

DA - 2012/8//

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/222079

ER -

## References

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

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.