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

Extension of the Decidability of the Marked PCP to Instances with Unique Blocks

Vesa Halava, Tero Harju, Juhani Karhumäki, Michel Latteux, Extension of the Decidability of the Marked PCP to Instances with Unique Blocks. Theoretical Computer Science 380(3), 355–362, 2007.

http://dx.doi.org/10.1016/j.tcs.2007.03.024

Abstract:

In the Post Correspondence Problem (PCP) an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists a nonempty word w such that h(w)=g(w). Here we prove that the PCP is decidable for instances with unique blocks using the decidability of the marked PCP. Also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. These results establish a new and larger class of decidable instances of the PCP, including the class of marked instances.

BibTeX entry:

@ARTICLE{jHaHaKaLa07a,
  title = {Extension of the Decidability of the Marked PCP to Instances with Unique Blocks},
  author = {Halava, Vesa and Harju, Tero and Karhumäki, Juhani and Latteux, Michel},
  journal = {Theoretical Computer Science},
  volume = {380},
  number = {3},
  pages = {355–362},
  year = {2007},
}

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

Publication Forum rating of this publication: level 2

Edit publication