A1 Refereed original research article in a scientific journal
Decidability of the binary infinite post correspondence problem
Authors: Halava V, Harju T, Karhumaki J
Publisher: ELSEVIER SCIENCE BV
Publication year: 2003
Journal:: Discrete Applied Mathematics
Journal name in source: DISCRETE APPLIED MATHEMATICS
Journal acronym: DISCRETE APPL MATH
Volume: 130
Issue: 3
First page : 521
Last page: 526
Number of pages: 6
ISSN: 0166-218X
DOI: https://doi.org/10.1016/S0166-218X(03)00330-5
Abstract
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.
UTU Research Portal