𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The post correspondence problem over a unary alphabet

✍ Scribed by P Rudnicki; G.J Woeginger

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
375 KB
Volume
16
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

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 becomes polynomially solvable if the input is encoded in unary.

πŸ“œ 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 ! =

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

On a generalization of the dyck-language
On a generalization of the dyck-language over a two letter alphabet
✍ Helmut Prodinger πŸ“‚ Article πŸ“… 1979 πŸ› Elsevier Science 🌐 English βš– 509 KB

Some properties of the language {w E (a, b}\* 1 d;) = (g)}, which can be regarded as a generalization of the (unrestricted) Dyck-language, are given. (Q are the binomial coefficients for words.)