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

On Post Correspondence Problem for Letter Monotonic Languages

Vesa Halava, Jarkko Kari, Yuri Matiyasevich, On Post Correspondence Problem for Letter Monotonic Languages. Theoretical Computer Science 410(30-32), 2957–2960, 2009.

Abstract:

We prove that for given morphisms g,h:{a1,a2,…,an}→B^*, it is decidable whether or not there exists a word w in the regular language View the MathML source such that g(w)=h(w). In other words, we prove that the Post Correspondence Problem is decidable if the solutions are restricted to be from this special language. This yields a nice example of an undecidable problem in integral matrices which cannot be directly proved undecidable using the traditional reduction from the Post Correspondence Problem.

BibTeX entry:

@ARTICLE{jHaKaMa09a,
  title = {On Post Correspondence Problem for Letter Monotonic Languages},
  author = {Halava, Vesa and Kari, Jarkko and Matiyasevich, Yuri},
  journal = {Theoretical Computer Science},
  volume = {410},
  number = {30-32},
  pages = {2957–2960},
  year = {2009},
}

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

Publication Forum rating of this publication: level 2

Edit publication