| Title:
|
Watson-Crick pushdown automata (English) |
| Author:
|
Chatterjee, Kingshuk |
| Author:
|
Ray, Kumar S. |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
53 |
| Issue:
|
5 |
| Year:
|
2017 |
| Pages:
|
868-876 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
deterministic Watson–Crick automata |
| Keyword:
|
deterministic Watson–Crick pushdown automata |
| Keyword:
|
deterministic multi-head pushdown automata |
| Keyword:
|
context free languages |
| MSC:
|
68Q10 |
| MSC:
|
68Q45 |
| idZBL:
|
Zbl 06861629 |
| idMR:
|
MR3750108 |
| DOI:
|
10.14736/kyb-2017-5-0868 |
| . |
| Date available:
|
2018-02-26T11:48:34Z |
| Last updated:
|
2018-05-25 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147098 |
| . |
| Reference:
|
[1] Chatterjee, K., Ray, K. S: Reversible Watson-Crick automata..Acta Informatica 54 (2017), 5, 487-499. MR 3673088, 10.1007/s00236-016-0267-0 |
| Reference:
|
[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. 10.1109/sfcs.1986.27 |
| Reference:
|
[3] Czeizler, E., Czeizler, E.: A short survey on Watson-Crick automata..Bull. EATCS 88 (2006), 104-119. MR 2222337 |
| Reference:
|
[4] Czeizler, E., Czeizler, E., Kari, L., Salomaa, K.: On the descriptional complexity of Watson-Crick automata..Theoretical Computer Science 410 (2009), 3250-3260. MR 2546880, 10.1016/j.tcs.2009.05.001 |
| Reference:
|
[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. MR 1688717, 10.1090/dimacs/048/22 |
| Reference:
|
[6] Harrison, M. A., Ibarra, O. H.: Multi-head and multi-tape pushdown automata..Inform. Control 13 (1968), 433-470. MR 0238622, 10.1016/s0019-9958(68)90901-7 |
| Reference:
|
[7] Hopcroft, J. E, Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. Third edition..Prentice Hall 2007. MR 0645539 |
| Reference:
|
[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. |
| Reference:
|
[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. MR 1850250, 10.1007/3-540-48321-7_34 |
| Reference:
|
[10] Paun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms..Springer-Verlag, Berlin, 1998. MR 1724525, 10.1007/978-3-662-03563-4 |
| Reference:
|
[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. MR 3424746, 10.1007/s11047-015-9494-5 |
| Reference:
|
[12] Samson, A. A.: 2-head pushdown automata..Procedia - Social and Behavioral Sciences 195 (2015), 2037-2046. 10.1007/s11047-015-9494-5 |
| . |
