Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong;  Qinghui Liu — 2012

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The infinite Post Correspondence Problem (PCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [36 (2003) 231–245] showed that PCP is undecidable for domain alphabets of size 105, Halava and Harju [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.

Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong;  Qinghui Liu — 2012

RAIRO - Theoretical Informatics and Applications

The infinite Post Correspondence Problem (PCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [ (2003) 231–245] showed that PCP is undecidable for domain alphabets of size 105, Halava and Harju [ (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.

Page 1

Download Results (CSV)