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

Decidability in Infinite Post Correspondence Problem

Vesa Halava, Decidability in Infinite Post Correspondence Problem. In: Proceedings of WORDS'03, TUCS General Publications, 382-391, 2003.

Abstract:

In the infinite Post Correspondence Problem an instance $(h,g)$
consists of two morphisms $h$ and $g$, both having the domain
alphabet of cardinality 2. The problem is to determine whether or
not there exist an infinite word $\omega$ such that $h(\omega) =
g(\omega)$. This problem is known to be undecidable for the
instances having unrestricted domain alphabets. Here we consider
the decidability proof of the special case where the morphisms are
marked. As a corollary, the decidability of the binary infinite
Post Correspondence Problem can be proved. This work is survey of
the two articles, [3] and [5].

BibTeX entry:

@INPROCEEDINGS{inpHalava03b,
  title = {Decidability in Infinite Post Correspondence Problem},
  booktitle = {Proceedings of  WORDS'03},
  author = {Halava, Vesa},
  number = {27},
  series = {TUCS General Publications},
  pages = {382-391},
  year = {2003},
}

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

Edit publication