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

Parallel Communicating Watson-Crick Automata Systems

Elena Czeizler, Eugen Czeizler, Parallel Communicating Watson-Crick Automata Systems. Acta Cybernetica 17(4), 685–700, 2006.

Abstract:

Watson-Crick automata are finite state automata working on
double-stranded tapes, introduced to investigate the potential of
DNA molecules for computing. In this paper we introduce the
concept of parallel communicating Watson-Crick automata systems. It
consists of several Watson-Crick finite automata parsing
independently the same input and exchanging information on
request, by communicating states to each other. We investigate the
computational power of these systems and prove that they are more
powerful than classical Watson-Crick finite automata, but still accepting
at most context-sensitive languages. Moreover, if the
complementarity relation is injective, then we obtain that this
inclusion is strict. For the general case, we also give some
closure properties, as well as a characterization of recursively
enumerable languages based on these systems.

Files:

Full publication in PDF-format

BibTeX entry:

@ARTICLE{jCzCz06c,
  title = {Parallel Communicating Watson-Crick Automata Systems},
  author = {Czeizler, Elena and Czeizler, Eugen},
  journal = {Acta Cybernetica},
  volume = {17},
  number = {4},
  pages = {685–700},
  year = {2006},
}

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

Publication Forum rating of this publication: level 1

Edit publication