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

(G)PCP for Words of Length at Most Two

Vesa Halava, Tero Harju, Mika Hirvensalo, Juhani Karhumäki, (G)PCP for Words of Length at Most Two. TUCS Technical Reports 463, Turku Centre for Computer Science, 2002.

Abstract:

We prove that the generalized Post Correspondence Problem is
undecidable in the case where the lengths of the words are at most two and
the size (or the number of pairs of words) is 32. The proof uses the
undecidability result of Tzeitin, namely the undecidability of the word
problem of a semigroup. We also transform our constructions in order to
achieve a proof for the undecidability of the Post Correspondence Problem
with images of length 1 or 2.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaHiKa02a,
  title = {(G)PCP for Words of Length at Most Two},
  author = {Halava, Vesa and Harju, Tero and Hirvensalo, Mika and Karhumäki, Juhani},
  number = {463},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2002},
  keywords = {Post Correspondence Problem, generalized Post Correspondence Problem, undecidability},
}

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

Edit publication