Equivalence of Subclasses of Two-Way Non-Deterministic Watson Crick Automata
ABSTRACT
Watson Crick automata are finite automata working on double strands. Extensive research work has already been done on non deterministic Watson Crick automata and on deterministic Watson Crick automata. Parallel Communicating Watson Crick automata systems have been introduced by E. Czeziler et al. In this paper we discuss about a variant of Watson Crick automata known as the two-way Watson Crick automata which are more powerful than non-deterministic Watson Crick automata. We also establish the equivalence of different subclasses of two-way Watson crick automata. We further show that recursively enumerable (RE) languages can be realized by an image of generalized sequential machine (gsm) mapping of two-way Watson-Crick automata.
Watson Crick automata are finite automata working on double strands. Extensive research work has already been done on non deterministic Watson Crick automata and on deterministic Watson Crick automata. Parallel Communicating Watson Crick automata systems have been introduced by E. Czeziler et al. In this paper we discuss about a variant of Watson Crick automata known as the two-way Watson Crick automata which are more powerful than non-deterministic Watson Crick automata. We also establish the equivalence of different subclasses of two-way Watson crick automata. We further show that recursively enumerable (RE) languages can be realized by an image of generalized sequential machine (gsm) mapping of two-way Watson-Crick automata.
Cite this paper
K. Ray, K. Chatterjee and D. Ganguly, "Equivalence of Subclasses of Two-Way Non-Deterministic Watson Crick Automata," Applied Mathematics, Vol. 4 No. 10, 2013, pp. 26-34. doi: 10.4236/am.2013.410A1005.
K. Ray, K. Chatterjee and D. Ganguly, "Equivalence of Subclasses of Two-Way Non-Deterministic Watson Crick Automata," Applied Mathematics, Vol. 4 No. 10, 2013, pp. 26-34. doi: 10.4236/am.2013.410A1005.
References
[1] L. C. S. Calude and G. Paun, “Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing,” Taylor & Francis Publishers, London, 2001. [2] L. M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems,” Science, New Series, Vol. 226, No. 5187, 1994, pp. 1021-1024. http://dx.doi.org/10.1126/science.7973651 [3] R. Freund, G. Paun, G. Rozenberg and A. Saloma, “A, Watson-Crick Finite Automata,” Proceedings of the 3rd DIMACS Workshop on DNA Based Computers, Philadelphia, 1997, pp. 297-328. [4] G. Paun, G. Rozenberg and A. Salomaa, “DNA Computing: New Computing Paradigms,” Springer-Verlag, Berlin, 1998. [5] E. Czeizler, E. Czeizler, L. Kari and K Salomaa, “WatsonCrick Automata: Determinism and State Complexity,” Proceeding of: 10th International Workshop on Descriptional Complexity of Formal Systems, DCFS, 16-18 July 2008, pp. 121-133. [6] E. Czeizler, E. Czeizler, L. Kari and K. Salomaa, “On the Descriptional Complexity of Watson-Crick Automata,” Theoretical Computer Science, Vol. 410, No. 35, 2009, pp. 3250-3260. http://dx.doi.org/10.1016/j.tcs.2009.05.001 [7] E. Czeizler, E. Czeizler,” Parallel Communicating Watson-Crick Automata Systems,” In: Z. Fulop Z. Esik (Ed.), Proceedings of 11th International Conference, AFL 2005, 2005, pp. 83-96. [8] E. Czeizler, “On the Power of Parallel Communicating Watson-Crick Automata Systems,” Theoretical Computer Science, Vol. 358, No. 1, 2006, pp. 142-147. [9] E. Czeizler, “A Short Survey on Watson-Crick Automata,” Bulletin of the EATCS, Vol. 88, 2006, pp. 104-119. [10] D. Kuske and P. Weigel, “The Role of the Complementarity Relation in Watson-Crick Automata and Sticker Systems,” Developments in Language Theory, Vol. 3340, Lecture Notes in Computer Science, Springer, Berlin, 2004, pp. 272-283. [11] M. Holzer, M. Kutrib and A. Malcher, “Multi-Head Finite Automata: Characterizations, Concepts and Open Problems,” Proceedings International Workshop on the Complexity of Simple Programs, Cork, 6-7 December 2008, pp. 93-107.
[1] L. C. S. Calude and G. Paun, “Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing,” Taylor & Francis Publishers, London, 2001. [2] L. M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems,” Science, New Series, Vol. 226, No. 5187, 1994, pp. 1021-1024. http://dx.doi.org/10.1126/science.7973651 [3] R. Freund, G. Paun, G. Rozenberg and A. Saloma, “A, Watson-Crick Finite Automata,” Proceedings of the 3rd DIMACS Workshop on DNA Based Computers, Philadelphia, 1997, pp. 297-328. [4] G. Paun, G. Rozenberg and A. Salomaa, “DNA Computing: New Computing Paradigms,” Springer-Verlag, Berlin, 1998. [5] E. Czeizler, E. Czeizler, L. Kari and K Salomaa, “WatsonCrick Automata: Determinism and State Complexity,” Proceeding of: 10th International Workshop on Descriptional Complexity of Formal Systems, DCFS, 16-18 July 2008, pp. 121-133. [6] E. Czeizler, E. Czeizler, L. Kari and K. Salomaa, “On the Descriptional Complexity of Watson-Crick Automata,” Theoretical Computer Science, Vol. 410, No. 35, 2009, pp. 3250-3260. http://dx.doi.org/10.1016/j.tcs.2009.05.001 [7] E. Czeizler, E. Czeizler,” Parallel Communicating Watson-Crick Automata Systems,” In: Z. Fulop Z. Esik (Ed.), Proceedings of 11th International Conference, AFL 2005, 2005, pp. 83-96. [8] E. Czeizler, “On the Power of Parallel Communicating Watson-Crick Automata Systems,” Theoretical Computer Science, Vol. 358, No. 1, 2006, pp. 142-147. [9] E. Czeizler, “A Short Survey on Watson-Crick Automata,” Bulletin of the EATCS, Vol. 88, 2006, pp. 104-119. [10] D. Kuske and P. Weigel, “The Role of the Complementarity Relation in Watson-Crick Automata and Sticker Systems,” Developments in Language Theory, Vol. 3340, Lecture Notes in Computer Science, Springer, Berlin, 2004, pp. 272-283. [11] M. Holzer, M. Kutrib and A. Malcher, “Multi-Head Finite Automata: Characterizations, Concepts and Open Problems,” Proceedings International Workshop on the Complexity of Simple Programs, Cork, 6-7 December 2008, pp. 93-107.