Undecidability of infinite post correspondence problem for instances of size 8
Jing Dong, Qinghui Liu (2012)
RAIRO - Theoretical Informatics and Applications
Similarity:
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...