Uni-transitional Watson–Crick D0L systems

✍ Scribed by Arto Salomaa

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 154 KB
• Volume: 281
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00026-9

✦ Synopsis

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 complementarity as a language-theoretic operation: "bad" words obtained through a generative process are replaced by their complementary ones. This idea seems particularly suitable for Lindenmayer systems. D0L systems augmented with a speciÿc complementarity transition, Watson-Crick D0L systems, have turned out to be a most interesting model and have already been extensively studied. A language is generated by a Watson-Crick D0L system as a sequence of words. Consequently, the systems can be applied also to compute functions in a natural way. In the present paper, attention is focused on uni-transitional systems, where at most one complementarity transition takes place in the generated sequence. In spite of their seeming simplicity, uni-transitional systems represent a vast extension of ordinary D0L systems. This becomes apparent in their capacity of deÿning functions. Quite remarkably, all basic decision problems for uni-transitional systems are algorithmically equivalent among themselves, as well as equivalent to a celebrated open problem. We investigate also a simpler case of systems with regular triggers, as well as pose some open problems.