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.


binary PCP, decidability, infinite words, post correspondence problem



Last updated on 14/10/2025 09:40:10 AM