• 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. In: Z. Fulop Z. Esik (Ed.), Proceedings of 11th International Conference, AFL 2005, 83-96, 2005.

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. If the complementarity
relation is also 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.

BibTeX entry:

@INPROCEEDINGS{inpCzCz05a,
  title = {Parallel Communicating Watson-Crick Automata Systems},
  booktitle = {Proceedings of 11th International Conference, AFL 2005},
  author = {Czeizler, Elena and Czeizler, Eugen},
  editor = {Z. Esik, Z. Fulop},
  pages = {83-96},
  year = {2005},
}

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

Edit publication