Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > On the Power of Parallel Commu...

On the Power of Parallel Communicating Watson-Crick Automata Systems

Elena Czeizler, Eugen Czeizler, On the Power of Parallel Communicating Watson-Crick Automata Systems. TUCS Technical Reports 722, Turku Centre for Computer Science, 2005.

Abstract:

Parallel communicating Watson-Crick automata systems were introduced in
[1] 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
[4], 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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tCzCz05a,
  title = {On the Power of Parallel Communicating Watson-Crick Automata Systems},
  author = {Czeizler, Elena and Czeizler, Eugen},
  number = {722},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2005},
  keywords = {Watson-Crick, parallel communicating automata systems, complementarity relation},
  ISBN = {952-12-1640-9},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication