Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong; Qinghui Liu

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

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

Abstract

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

How to cite

top

Dong, 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. [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. [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. [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. [4] V. Halava, T. Harju and M. Hirvensalo, Binary (generalized) Post Correspondence Problem. Theoret. Comput. Sci.276 (2002) 183–204. Zbl1023.03038MR1896352
  5. [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. [6] E. Post, A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc.52 (1946) 264–268. Zbl0063.06329MR15343
  7. [7] K. Ruohonen, Reversible machines and Posts Correspondence Problem for biprefix morphisms. J. Inform. Process. Cybernet.EIK21 (1985) 579–595. Zbl0604.68057MR825861

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.