Undecidability of infinite post correspondence problem for instances of Size 9
Department of Mathematics and TUCS – Turku Centre for Computer
Science, University of Turku, 20014 Turku, Finland;
Accepted: 16 September 2005
In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word ω such that h(ω) = g(ω). This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini (Theory Comput. Syst. 36 (2003) 231–245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable for instances where the morphisms have domains of 9 letters. The proof uses a recent result of Matiyasevich and Sénizergues and a modification of a result of Claus.
Mathematics Subject Classification: 03D35 / 03D40 / 68R15
Key words: Infinite Post Correspondence Problem / undecidability / word problem / semi–Thue system.
© EDP Sciences, 2006