RAIRO - Theoretical Informatics and Applications

Research Article

Undecidability of infinite post correspondence problem for instances of size 8

Jing Donga1 and Qinghui Liua1

a1 Dept. Comput. Sci., Beijing Institute of Technology, Beijing 100081, P.R. China. dongjing@bit.edu.cn; qhliu@bit.edu.cn

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.

(Received November 11 2011)

(Accepted May 9 2012)

(Online publication June 22 2012)

Key Words:

  • ωPCP;
  • semi-Thue system;
  • undecidable;
  • theory of computation

Mathematics Subject Classification:

  • 03D35;
  • 03D40;
  • 68R15
Metrics