Title of article
Decidability of the binary infinite Post Correspondence Problem
Author/Authors
Vesa Halava، نويسنده , , Tero Harju، نويسنده , , Juhani Karhumaki، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2003
Pages
6
From page
521
To page
526
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 ω is an infinite word ω=a1a2… such that h(ω)=g(ω). This problem is known to be undecidable for the unrestricted instances of the Post Correspondence Problem.
Keywords
Decidability , Binary PCP , Infinite words , Post Correspondence Problem
Journal title
Discrete Applied Mathematics
Serial Year
2003
Journal title
Discrete Applied Mathematics
Record number
885670
Link To Document