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

Post Correspondence Problem for Short Words

Vesa Halava, Tero Harju, Mika Hirvensalo, Juhani Karhumäki, Post Correspondence Problem for Short Words. Information Processing Letters 108(3), 115–118 , 2008.

http://dx.doi.org/10.1016/j.ipl.2008.04.013

Abstract:

We prove that the generalized Post Correspondence Problem is undecidable for instances where the lengths of the image words are at most 2 and the number of pairs of words is at most 30. The proof uses undecidability of the word problem of the Tzeitin semigroup. We also transform our constructions in order to achieve a proof for the undecidability of the (not generalized) Post Correspondence Problem with image words of length at most 2.

BibTeX entry:

@ARTICLE{jHaHaHiKa08a,
  title = {Post Correspondence Problem for Short Words},
  author = {Halava, Vesa and Harju, Tero and Hirvensalo, Mika and Karhumäki, Juhani},
  journal = {Information Processing Letters},
  volume = {108},
  number = {3},
  pages = {115–118 },
  year = {2008},
}

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

Publication Forum rating of this publication: level 2

Edit publication