Some Relations between Watson-Crick Finite Automata and Chomsky Hierarchy

Sadaki HIROSE  Kunifumi TSUDA  Yasuhiro OGOSHI  Haruhiko KIMURA  

IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.5   pp.1261-1264
Publication Date: 2004/05/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Automata and Formal Language Theory
Watson-Crick automaton,  DNA computing,  formal language,  automaton,  

Full Text: PDF>>
Buy this Article

Watson-Crick automata, recently introduced in, are new types of automata in the DNA computing framework, working on tapes which are double stranded sequences of symbols related by a complementarity relation, similar to a DNA molecule. The automata scan separately each of the two strands in a corelated mannar. Some restricted variants of them were also introduced and the relationship between the families of languages recognized by them were investigated in. In this paper, we clarify some relations between the families of languages recognized by the restricted variants of Watson-Crick finite automata and the families in the Chomsky hierarchy.