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
topHow 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.
- 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.
- V. Halava and T. Harju, Undecibability of infinite Post Correspondence Problem for instances of size 9. RAIRO–Theor. Inf. Appl.40 (2006) 551–557.
- V. Halava, T. Harju and M. Hirvensalo, Binary (generalized) Post Correspondence Problem. Theoret. Comput. Sci.276 (2002) 183–204.
- Y. Matiyasevich and G. Sénizergues, Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci.330 (2005) 145–169.
- E. Post, A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc.52 (1946) 264–268.
- K. Ruohonen, Reversible machines and Posts Correspondence Problem for biprefix morphisms. J. Inform. Process. Cybernet.EIK21 (1985) 579–595.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.