Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
deterministic Watson–Crick automata; deterministic Watson–Crick pushdown automata; deterministic multi-head pushdown automata; context free languages
deterministic Watson–Crick automata; deterministic Watson–Crick pushdown automata; deterministic multi-head pushdown automata; context free languages
Summary:
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.
References:
[1] Chatterjee, K., Ray, K. S: Reversible Watson-Crick automata. Acta Informatica 54 (2017), 5, 487-499. DOI 10.1007/s00236-016-0267-0 | MR 3673088
[2] Chrobak, M., Li, M.: $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] Czeizler, E., Czeizler, E.: A short survey on Watson-Crick automata. Bull. EATCS 88 (2006), 104-119. MR 2222337
[4] Czeizler, E., Czeizler, E., Kari, L., Salomaa, K.: On the descriptional complexity of Watson-Crick automata. Theoretical Computer Science 410 (2009), 3250-3260. DOI 10.1016/j.tcs.2009.05.001 | MR 2546880
[5] Freund, R., G.Paun, G.Rozenberg, 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 | MR 1688717
[6] Harrison, M. A., Ibarra, O. H.: Multi-head and multi-tape pushdown automata. Inform. Control 13 (1968), 433-470. DOI 10.1016/s0019-9958(68)90901-7 | MR 0238622
[7] Hopcroft, J. E, Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. Third edition. Prentice Hall 2007. MR 0645539
[8] Nagy, B.: 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.
[9] Paun, A., Paun, M.: 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 | MR 1850250
[10] Paun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer-Verlag, Berlin, 1998. DOI 10.1007/978-3-662-03563-4 | MR 1724525
[11] Ray, K. S., Chatterjee, K., Ganguly, D.: 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 | MR 3424746
[12] Samson, A. A.: 2-head pushdown automata. Procedia - Social and Behavioral Sciences 195 (2015), 2037-2046. DOI 10.1007/s11047-015-9494-5
Search
Partner of
