Watson-Crick Automata and PCFAS with Two Components-A Computational Power Analogy-

摘要

Watson-Crick Automata are a counterpart of finite automata working on a Watson-Crick tape composed of double stran- ded sequences of symbols linked by a complementarity rela- tion like DNA molecules.Consequently,these devices have as input double strands of strings of symbols arranged in a pairwise a?nity similar to Watson-Crick complementarity given by the pairs of nucleotides(A,T)and(C,G)of the DNA alphabet.They have been created in order to investi- gate the behaviour of DNA molecules. rnParallel Communicating Finite Automata Systems are ac- cepting devices composed of two or more finite automata that work in parallel in a synchronized manner,communi- cating states to each other by request.The protocol of col- laboration is controlled by the so-called query symbols.They impose restrictions in the communication process(they spec- ify which automaton has to provide its current state to the automaton that asked for the information).Depending on this protocol several variants of parallel communicating fi- nite automata systems have been introduced in the litera- ture,e.g.returning or not returning,centralized or not. rnIn this paper we prove that Watson-Crick automata and parallel communicating finite automata systems with two components are equivalent from a computational point of view.This statement does not depend on the type of the system protocol.We use this result in solving two open problems that concern the characterization of recursively enumerable languages with parallel communicating devices. Several examples,given at the end of the paper,illustrate possible application of the above systems in DNA computing, more exactly in the process of gene assembly in ciliates.