Undecidability of infinite post correspondence problem for instances of size 9



: Halava V, Harju T

Publisher: EDP SCIENCES S A

: 2006

: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications

: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS

: RAIRO-THEOR INF APPL

: 40

: 4

: 551

: 557

: 7

: 0988-3754

DOI: https://doi.org/10.1051/ita:2006039


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 omega such that h(omega) = g(omega). 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 Senizergues and a modification of a result of Claus.



Last updated on 2025-14-10 at 09:55