• 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