In Chapter 6, we study models which combine formal language theory and Watson-Crick complementarity, a fundamental concept of DNA computing.
For a longer introduction into DNA computing see the introductory part of Chapter 6, here we simply note that the effectivity of computing by DNA is thought to originate from two properties: massive parallelism and the phenomenon of Watson-Crick complementarity, which motivates the intensive research done on Watson-Crick complementarity in formal language theory.
From our point of view Watson-Crick complementarity provides a new operation. For each letter of the alphabet there exists a complementary symbol, thus for each word there exists a complementary word. In a Watson-Crick system during the derivation, when some conditions hold on the computed string, the computation continues from the complementary string. It is Watson-Crick complementarity that makes it possible to suppose that this complementary word is always present.
Our main goal is to examine the effect of introducing Watson-Crick complementarity into the framework of eco-grammar systems, in this chapter however, we do not restrict our investigation to the eco-grammar system models but study Lindenmayer systems as well. We follow this approach because the techniques presented for Lindenmayer systems, with only a slight modification, are also useful when combining simple eco-grammar systems and Watson-Crick complementarity.
Watson-Crick D0L system, the first model in formal language theory using Watson-Crick complementarity as an operation, was introduced and first studied in [Mihalache and SalomaaMihalache and Salomaa1997] and [Mihalache and SalomaaMihalache and Salomaa2001]. This model raises a lot of interesting questions for study, such as the stability, the periodicity, and the growth functions of these systems. For further information see [SalomaaSalomaa1998], [SalomaaSalomaa1999], [SalomaaSalomaa2001a], [SalomaaSalomaa2001b], [Honkala and SalomaaHonkala and Salomaa2001], [Csuhaj-Varjú and SalomaaCsuhaj-Varjú and Salomaa2000].
The computational capacity of these constructs is also among the particularly important problems. In [SosikSosik2001] it was shown that any Turing computable function can be computed by a Watson-Crick D0L system.
In Chapter 6 first we also study the problem of the generating power of several variants of standard Watson-Crick Lindenmayer systems: we study standard Watson-Crick tabled EDT0L systems and standard Watson-Crick E0L systems. In the first case the environmental component of the system is represented by more than one deterministic Lindenmayer set, in the latter the environment has only one set, but this set is not necessarily deterministic. The adjective ``standard'' refers, in both cases, to the mechanism triggering the complementary transitions during the derivation. We show that all recursively enumerable languages can be generated by both types of systems.
Although these results are about Lindenmayer systems and not about eco-grammar systems, they are presented however because the constructions of their proofs are useful when examining standard Watson-Crick eco-grammar systems, which emerges from extended simple eco-grammar systems by adding the general idea of Watson-Crick complementarity. The functioning of a standard Watson-Crick eco-grammar system is similar to the original (i.e. non-Watson-Crick) case, with the only difference that when during the computation the sentential form satisfies some requirements, it is replaced by its complementary string. We prove that standard Watson-Crick eco-grammar systems with only one agent are able to generate all recursively enumerable languages.