𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Watson–Crick D0L systems: the power of one transition

✍ Scribed by Arto Salomaa; Petr Sosı́k

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
254 KB
Volume
301
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We investigate the class of functions computable by uni-transitional Watson-Crick D0L systems: only one complementarity transition is possible during each derivation. The class is characterized in terms of a certain min-operation applied to Z-rational functions. We also exhibit functions outside the class, and show that the basic decision problems are equivalent or harder than a celebrated open problem. For instance, the latter alternative applies to the growth-bound problem for functions in the class.

📜 SIMILAR VOLUMES

Uni-transitional Watson–Crick D0L system
Uni-transitional Watson–Crick D0L systems
✍ Arto Salomaa 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 154 KB

The phenomenon known as Watson-Crick complementarity is basic both in the experiments and theory of DNA computing. While the massive parallelism of DNA strands makes exhaustive searches possible, complementarity constitutes a powerful computational tool. It is also very fruitful to view complementar

On images of D0L and DT0L power series
On images of D0L and DT0L power series
✍ Juha Honkala 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 151 KB

The D0L and DT0L power series are generalizations of D0L and DT0L languages. We continue the study of these series by investigating various decidability questions concerning the images of D0L and DT0L power series.