We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes.
- Authors
Sears, David; Salomaa, Kai
- Abstract
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.
- Subjects
L systems; MACHINE theory; SET theory; FORMAL languages; MATHEMATICAL models
- Publication
Natural Computing, 2012, Vol 11, Issue 4, p653
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-012-9329-6