A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Decidability of the binary infinite post correspondence problem
Tekijät: Halava V, Harju T, Karhumaki J
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2003
Lehti:: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: DISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Vuosikerta: 130
Numero: 3
Aloitussivu: 521
Lopetussivu: 526
Sivujen määrä: 6
ISSN: 0166-218X
DOI: https://doi.org/10.1016/S0166-218X(03)00330-5
Tiivistelmä
We shall show that it is decidable for binary instances of the Post Correspondence Problem whether the instance has an infinite solution. In this context, a binary instance (h,g) consists of two morphisms h and g with a common two element domain alphabet. An infinite solution omega is an infinite word (omega) =a(1)a(2)... such that h(omega) = g(omega). This problem is known to be undecidable for the unrestricted instances of the Post Correspondence Problem. (C) 2003 Elsevier B.V. All rights reserved.
We shall show that it is decidable for binary instances of the Post Correspondence Problem whether the instance has an infinite solution. In this context, a binary instance (h,g) consists of two morphisms h and g with a common two element domain alphabet. An infinite solution omega is an infinite word (omega) =a(1)a(2)... such that h(omega) = g(omega). This problem is known to be undecidable for the unrestricted instances of the Post Correspondence Problem. (C) 2003 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali