Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes
Watson-Crick Lindenmayer systems add a control mechanism to ordinary Lindenmayer (L) system derivations. The mechanism is inspired by the complementarity relation in DNA strings, and it is formally defined in terms of a trigger language (trigger, for short). It is known that Watson-Crick E0L systems employed with the standard trigger (which is a context-free language) are computationally universal. Here we show that all recursively enumerable languages can be generated already by a Uni-Transitional Watson-Crick E0L system with a regular trigger. A system is Uni-Transitional if any derivation of a terminal word can apply the Watson-Crick morphism at most once. We introduce a weak derivation mode where, for sentential forms in the trigger language, the derivation chooses nondeterministically whether or not to apply the Watson-Crick morphism. We show that Watson-Crick E0L systems employing a regular trigger and the weak derivation mode remain computationally universal but, on the other hand, the corresponding Uni-Transitional systems generate only a subclass of the ET0L languages. We consider also the computational power of Watson-Crick (deterministic) ET0L systems.
lindenmayer systems e0l systems recursively enumerable language computational power dna computing watson-crick complementarity