• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Decidability of Binary Infinite Post Correspondence Problem

Vesa Halava, Tero Harju, Juhani Karhumäki, Decidability of Binary Infinite Post Correspondence Problem. Discrete Applied Mathematics 130, 521–526, 2003.

Abstract:

We shall show that is 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_1a_2 \dots$
such that $h(\omega) = g(\omega)$. This problem is known to be
undecidable for the unrestricted instances of the Post Correspondence
Problem.

BibTeX entry:

@ARTICLE{jHaHaKa03a,
  title = {Decidability of Binary Infinite Post Correspondence Problem},
  author = {Halava, Vesa and Harju, Tero and Karhumäki, Juhani},
  journal = {Discrete Applied Mathematics},
  volume = {130},
  pages = {521–526},
  year = {2003},
  keywords = {Post Correspondence Problem, Infinite words, Decidability, Binary PCP},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication