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

The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems

Vesa Halava, Tero Harju, Juhani Karhumäki, The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems. Theory of Computing Systems 40(1), 43–54, 2007.

http://dx.doi.org/10.1007/s00224-005-1222-6

Abstract:

In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word ω such that h(ω) = g(ω). This problem is undecidable in general, but it is known to be decidable for binary and marked instances. A morphism is binary if the domain alphabet is of size 2, and marked if each image of a letter begins with a different letter. We prove that the solutions of a marked instance form a set E ω ⋃ E * (P ⋃ F), where P is a finite set of ultimately periodic words, E is a finite set of solutions of the PCP, and F is a finite set of morphic images of fixed points of D0L systems. We also establish the structure of infinite solutions of the binary PCP.

BibTeX entry:

@ARTICLE{jHaHaKa07b,
  title = {The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems},
  author = {Halava, Vesa and Harju, Tero and Karhumäki, Juhani},
  journal = {Theory of Computing Systems},
  volume = {40},
  number = {1},
  pages = {43–54},
  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