• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the Power of Parallel Communicating Watson-Crick Automata Systems

Elena Czeizler, Eugen Czeizler, On the Power of Parallel Communicating Watson-Crick Automata Systems. Theoretical Computer Science 358(1), 142–147, 2006.

Abstract:

Parallel communicating Watson–Crick automata systems were introduced in [E. Czeizler, E. Czeizler, Parallel communicating Watson–Crick automata systems, in: Z. Ésik, Z. Fülöp (Eds.), Proc. Automata and Formal Languages, Dobogókő, Hungary, 2005, pp. 83–96] 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 [D. Kuske, P. Weigel, The Role of the Complementarity Relation in Watson–Crick Automata and Sticker Systems, DLT 2004, Lecture Notes in Computer Science, Vol. 3340, Auckland, New Zealand, 2004, pp. 272–283], 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.

BibTeX entry:

@ARTICLE{jCzCz06b,
  title = {On the Power of Parallel Communicating Watson-Crick Automata Systems},
  author = {Czeizler, Elena and Czeizler, Eugen},
  journal = {Theoretical Computer Science},
  volume = {358},
  number = {1},
  publisher = {Elsevier},
  pages = {142–147},
  year = {2006},
  keywords = {Watson–Crick; Parallel communicating automata systems; Complementarity relation },
}

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

Publication Forum rating of this publication: level 2

Edit publication