Decidability of the binary infinite post correspondence problem

: Halava V, Harju T, Karhumaki J

Publisher: ELSEVIER SCIENCE BV

: 2003

Discrete Applied Mathematics

DISCRETE APPLIED MATHEMATICS

: DISCRETE APPL MATH

: 130

: 3

: 521

: 526

: 6

: 0166-218X

DOI: https://doi.org/10.1016/S0166-218X(03)00330-5

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.

Mathematics