Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > The Post Correspondence Proble...

The Post Correspondence Problem for Marked Morphisms

Vesa Halava, The Post Correspondence Problem for Marked Morphisms. TUCS Dissertations 37. Turku Centre for Computer Science, 2002.

Abstract:

In 1982 Ehrenfeucht, Karhumåki and Rozenberg proved that the
marked generalized Post Correspondence Problem is decidable in the case
of binary morphisms. The main result of the thesis is an extension of this
result for alphabets of arbitrary size. We first prove that the Post
Correspondence Problem is decidable for marked morphisms and then use
the same idea for the above stated extension. As a corollary we obtain a
new, and somewhat shorter, proof for the decidability of the binary Post
Correspondence Problem.

Our result yields some new results in searching for the borderline of
decidability and undecidability. The marked morphisms form a special case
of prefix morphisms, and it was shown by Ruohonen in 1985 that the Post
Correspondence Problem is undecidable for prefix morphisms. Therefore,
the borderline of decidability and undecidability is somewhere between
these two cases. Indeed, the morphisms constructed by Ruohonen were
strongly 5--marked. The decidability status of the Post Correspondence
remains open for strongly k-marked instances for k between 2 and 4.

We also prove that the 2--marked Post Correspondence Problem, where we
do not require the injectivity, is undecidable, and this also gives us more
information on the borderline of decidability and undecidability.

We also present two recent undecidability results. The first one is the
undecidability of the Post Correspondence Problem in the case where the
morphisms are permutations of each other, and the second one is a special
universe problem concerning the equality set of two morphisms. The
usefulness of these undecidability results will be seen in the future.

Important open problems concerning Post Correspondence Problem are
stated in the thesis.

Files:

Full publication in PDF-format

BibTeX entry:

@PHDTHESIS{phdHalava02a,
  title = {The Post Correspondence Problem for Marked Morphisms},
  author = {Halava, Vesa},
  number = {37},
  series = {TUCS Dissertations},
  school = {Turku Centre for Computer Science},
  year = {2002},
  keywords = {Post Correspondence Problem, marked morphisms, generalized Post Correspondence Problem, decidability, undecidability},
  ISBN = {951-29-2263-0},
}

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

Edit publication