Uni-transitional Watson–Crick D0L systems

AbstractThe 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 specific 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 defining 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