Some Relationships between Classes of Reverse Watson-Crick Finite Automata

Authors: Kazuki Murakami, Takashige Nakamura, Noriko Sakamoto, Kunio Aizawa

Abstract:

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.

Keywords: automaton, DNA computing, formal languages, Watson-Crick automaton

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330333

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.