A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Undecidability of infinite post correspondence problem for instances of size 9
Tekijät: Halava V, Harju T
Kustantaja: EDP SCIENCES S A
Julkaisuvuosi: 2006
Lehti:: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Tietokannassa oleva lehden nimi: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Lehden akronyymi: RAIRO-THEOR INF APPL
Vuosikerta: 40
Numero: 4
Aloitussivu: 551
Lopetussivu: 557
Sivujen määrä: 7
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita:2006039
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali