Some Relationships between Classes of Reverse Watson-Crick Finite Automata

A Watson-Crick automaton is recently introduced as a computational model of DNA computing framework. It works on tapes consisting of double stranded sequences of symbols. Symbols placed on the corresponding cells of the double-stranded sequences are related by a complimentary relation. In this paper, we investigate a variation of Watson-Crick automata in which both heads read the tape in reverse directions. They are called reverse Watson-Crick finite automata (RWKFA). We show that all of following four classes, i.e., simple, 1-limited, all-final, all-final and simple, are equal to non-restricted version of RWKFA.

Authors:

• Kazuki Murakami
• Takashige Nakamura
• Noriko Sakamoto
• Kunio Aizawa

Keywords:

• automaton
• DNA computing
• formal languages
• Watson-Crick automaton

References:

[1] G. Pâun, G. Rozenberg, and A. Salomaa, DNA Computing, New
Computing Paradigms. Springer-Verlag, 1998, ch. 5.
[2] R. Freund, G. Pâun, G. Rozenberg, and A. Salomaa, "Watson-Crick finite
automata," in Proc. of the Third Annual DIMACS Symp on DNA Based
Computers, Philadelphia, 1997, pp. 305-317.
[3] S. Hirose, K. Tsuda, Y. Ogoshi, and H. Kimura, "Some relations between
Watson-Crick finite automata and Chomsky hierarchy," IEICE Trans. on
Information and Systems, E89-D (10), 2006, pp. 2591-2599.
[4] S. Okawa and S. Hirose, "The relations among Watson-Crick automata
and their relations with context-free languages," IEICE Trans. on
Information and Systems, E87-D (5), 2004, pp. 1261-1264.
[5] D. Kuske and P. Weigel, "The role of the complementarity relations in
Watson-Crick automata and sticker systems," in Proc. of DLT 2004,
Lecture Notes in Computer Science, 3340, Springer-Verlag, 2004, pp.
272-283.
[6] B. Nagy, "On 5-3- sensing Watson-Crick finite automata," in Proc. of
DNA 13, Lecture Notes in Computer Science, 4848, Springer-Verlag,
2007, pp. 256-262.
[7] B. Nagy, "On a hierarchy of 5-3- Sensing WK finite automata
langugaes," in Proc. of 5th Conference on Computability in Europe, CiE
2009, Hidelberg, Germany, 2009, 266-275.