Watson-Crick finite automata have been introduced as a possible model of DNA computation. They differ from their classical counterpart in that they are capable of working on double-stranded sequences. The strands are processed by two independent heads of the automaton. The movement of the heads is controlled by a single state. The characters that appear “on the corresponding positions of the two strands are connected by a complementarity relation” similar to the Watson-Crick complementarity of DNA nucleotides (Watson-Crick base pairings).
In [1], the authors emphasized that “the high hopes for the future of DNA computing are based on two fundamental features: (i) the massive parallelism of DNA strands, [and] (ii) Watson-Crick complementarity.” In an attempt to combine these two features into a DNA computing model, instead of using a single Watson-Crick finite automaton, Czeizler and Czeizler, in [2], proposed to consider “a set of Watson-Crick finite automata working independently on their own input tapes” (the input is the same on all of those tapes) and communicating with each other by special states on request. The combination is known as parallel communicating Watson-Crick automata systems.
These systems turned out to be more powerful than parallel communicating finite automata. They recognize all languages accepted by the latter and also some others, such as a non-regular unary language L={ an2 | n ≥ 2 }. In particular, in [3], it was proved that L is “accepted by a parallel communicating Watson-Crick automata [having] three components and a non-injective complementarity relation.”
This paper offers an improvement of that result. The authors show that parallel communicating Watson-Crick automata systems with just two components and a non-injective complementarity relation are powerful enough to accept L. Furthermore, they also prove that one component only is not sufficient to accept a unary non-regular language.
This short paper proves an interesting technical result. It would have been good if more general context and the importance of the result were also discussed.
