A1 Refereed original research article in a scientific journal
Undecidability of infinite post correspondence problem for instances of size 9
Authors: Halava V, Harju T
Publisher: EDP SCIENCES S A
Publication year: 2006
Journal:: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Journal name in source: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Journal acronym: RAIRO-THEOR INF APPL
Volume: 40
Issue: 4
First page : 551
Last page: 557
Number of pages: 7
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita:2006039
Abstract
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.
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.
UTU Research Portal