For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Some Relations between Watson-Crick Finite Automata and Chomsky Hierarchy
Sadaki HIROSE Kunifumi TSUDA Yasuhiro OGOSHI Haruhiko KIMURA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/05/01
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>>
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.