Parallel Communicating Watson-Crick Automata Systems

Parallel communicating Watson-Crick automata systems were introduced in [2] as possible models of DNA computations. This combination of Watson-Crick automata and parallel communicating systems comes as a natural extension due to the new developments in DNA manipulation techniques. It is already known, see [5], that for Watson-Crick finite automata, the complementarity relation plays no active role. However, this is not the case when considering parallel communicating Watson-Crick automata systems. In this paper we prove that non-injective complementarity relations increase the accepting power of these systems. We also prove that although Watson-Crick automata are equivalent to two-head finite automata, this equivalence is not preserved when comparing parallel communicating Watson-Crick automata systems and multi-head finite automata. Key words: Watson-Crick, Parallel communicating automata systems, Complementarity relation