𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Flatwords and Post Correspondence Problem

✍ Scribed by Tero Harju; Marjo Lipponen; Alexandru Mateescu

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
886 KB
Volume
161
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Decidability of the binary infinite Post
Decidability of the binary infinite Post Correspondence Problem
✍ Vesa Halava; Tero Harju; Juhani KarhumΓ€ki πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 115 KB

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 ! =

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