Commenced in January 2007
Paper Count: 31103
Some Relationships between Classes of Reverse Watson-Crick Finite Automata
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330333Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1204
 G. Pâun, G. Rozenberg, and A. Salomaa, DNA Computing, New Computing Paradigms. Springer-Verlag, 1998, ch. 5.
 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.
 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.
 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.
 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.
 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.
 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.