𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decidability of the binary infinite Post Correspondence Problem

✍ Scribed by Vesa Halava; Tero Harju; Juhani Karhumäki

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
115 KB
Volume
130
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We shall show that it is decidable for binary instances of the Post Correspondence Problem whether the instance has an inÿnite solution. In this context, a binary instance (h; g) consists of two morphisms h and g with a common two element domain alphabet. An inÿnite solution ! is an inÿnite word ! = a1a2 : : : such that h(!) = g(!). This problem is known to be undecidable for the unrestricted instances of the Post Correspondence Problem.

📜 SIMILAR VOLUMES

The post correspondence problem over a u
The post correspondence problem over a unary alphabet
✍ P Rudnicki; G.J Woeginger 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 375 KB

consider the problem of finding a shortest solution for the Post correspondence problem over a unary alphabet. We show that the complexity of this problem heavily depends on the representation of the input: the problem is NP-complete if the input is given in compact (logarithmic) form, whereas it be

Using DNA to solve the Bounded Post Corr
Using DNA to solve the Bounded Post Correspondence Problem
✍ Lila Kari; Greg Gloor; Sheng Yu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 121 KB

Theoretical research in DNA computing includes designing practical experiments for solving various computational problems by means of DNA manipulation. This paper proposes a DNA algorithm for an NP-complete problem, The Bounded Post Correspondence Problem. The proposed experiment can be used to test