Kybernetika 53 no. 5, 868-876, 2017

Watson-Crick pushdown automata

Kingshuk Chatterjee and Kumar S. RayDOI: 10.14736/kyb-2017-5-0868

Abstract:

A multi-head 1-way pushdown automaton with $k$ heads is a pushdown automaton with $k$ 1-way read heads on the input tape and a stack. It was previously shown that the deterministic variant of the model cannot accept all the context free languages. In this paper, we introduce a 2-tape, 2-head model namely Watson-Crick pushdown automata where the content of the second tape is determined using a complementarity relation, similar to Watson-Crick automata. We show computational powers of nondeterministic two-head pushdown automata and nondeterministic Watson-Crick pushdown automata are same. Moreover, deterministic Watson-Crick pushdown automata can accept all the context free languages.

Keywords:

deterministic Watson-Crick automata, deterministic Watson-Crick pushdown automata, deterministic multi-head pushdown automata, context free languages

Classification:

68Q45, 68Q10

paper.pdf

References:

  1. K. Chatterjee and K. S Ray: Reversible Watson-Crick automata. Acta Informatica 54 (2017), 5, 487-499.   DOI:10.1007/s00236-016-0267-0
  2. M. Chrobak and M. Li: $k$+1 heads are better than k for PDA's. In: Proc. 27th Annual Symp. on Foundations of Computer Science 1986, pp. 361-367.   DOI:10.1109/sfcs.1986.27
  3. E. Czeizler and E. Czeizler: A short survey on Watson-Crick automata. Bull. EATCS 88 (2006), 104-119.   CrossRef
  4. E. Czeizler, E. Czeizler, L. Kari and K. Salomaa: On the descriptional complexity of Watson-Crick automata. Theoretical Computer Science 410 (2009), 3250-3260.   DOI:10.1016/j.tcs.2009.05.001
  5. R. Freund, G.Paun, G.Rozenberg and A.Salomaa: Watson-Crick finite automata. In: Proc. 3rd DIMACS Workshop on DNA Based Computers, Philadelphia 1997, pp. 297-328.   DOI:10.1090/dimacs/048/22
  6. M. A. Harrison and O. H. Ibarra: Multi-head and multi-tape pushdown automata. Inform. Control 13 (1968), 433-470.   DOI:10.1016/s0019-9958(68)90901-7
  7. J. E Hopcroft, R. Motwani and J. D. Ullman: Introduction to Automata Theory, Languages and Computation. Third edition. Prentice Hall 2007.   CrossRef
  8. B. Nagy: A family of two-head pushdown automata. In: NCMA 2015: 7th Workshop on Non Classical Models of Automata and Applications, Porto 2015, pp. 177-191.   CrossRef
  9. A. Paun and M. Paun: State and transition complexity of Watson-Crick finite automata. Fundamentals of Computation Theory, Lecture Notes in Computer Science 1684 (1999), 409-420.   DOI:10.1007/3-540-48321-7_34
  10. G. Paun, G. Rozenberg and A. Salomaa: DNA Computing: New Computing Paradigms. Springer-Verlag, Berlin, 1998.   DOI:10.1007/978-3-662-03563-4
  11. K. S. Ray, K. Chatterjee and D. Ganguly: State complexity of deterministic Watson-Crick automata and time varying Watson-Crick automata. Nat. Comput. 14 (2015), 691-699.   DOI:10.1007/s11047-015-9494-5
  12. A. A. Samson: 2-head pushdown automata. Procedia - Social and Behavioral Sciences 195 (2015), 2037-2046.   DOI:10.1007/s11047-015-9494-5