Watson-Crick pushdown automata

Kingshuk Chatterjee; Kumar S. Ray

Kybernetika (2017)

  • Volume: 53, Issue: 5, page 868-876
  • ISSN: 0023-5954

Abstract

top
A multi-head 1-way pushdown automaton with heads is a pushdown automaton with 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.

How to cite

top

Chatterjee, Kingshuk, and Ray, Kumar S.. "Watson-Crick pushdown automata." Kybernetika 53.5 (2017): 868-876. <http://eudml.org/doc/294672>.

@article{Chatterjee2017,
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.},
author = {Chatterjee, Kingshuk, Ray, Kumar S.},
journal = {Kybernetika},
keywords = {deterministic Watson–Crick automata; deterministic Watson–Crick pushdown automata; deterministic multi-head pushdown automata; context free languages},
language = {eng},
number = {5},
pages = {868-876},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Watson-Crick pushdown automata},
url = {http://eudml.org/doc/294672},
volume = {53},
year = {2017},
}

TY - JOUR
AU - Chatterjee, Kingshuk
AU - Ray, Kumar S.
TI - Watson-Crick pushdown automata
JO - Kybernetika
PY - 2017
PB - Institute of Information Theory and Automation AS CR
VL - 53
IS - 5
SP - 868
EP - 876
AB - 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.
LA - eng
KW - deterministic Watson–Crick automata; deterministic Watson–Crick pushdown automata; deterministic multi-head pushdown automata; context free languages
UR - http://eudml.org/doc/294672
ER -

References

top
  1. Chatterjee, K., Ray, K. S, 10.1007/s00236-016-0267-0, Acta Informatica 54 (2017), 5, 487-499. MR3673088DOI10.1007/s00236-016-0267-0
  2. Chrobak, M., Li, M., 10.1109/sfcs.1986.27, In: Proc. 27th Annual Symp. on Foundations of Computer Science 1986, pp. 361-367. DOI10.1109/sfcs.1986.27
  3. Czeizler, E., Czeizler, E., A short survey on Watson-Crick automata., Bull. EATCS 88 (2006), 104-119. MR2222337
  4. Czeizler, E., Czeizler, E., Kari, L., Salomaa, K., 10.1016/j.tcs.2009.05.001, Theoretical Computer Science 410 (2009), 3250-3260. MR2546880DOI10.1016/j.tcs.2009.05.001
  5. Freund, R., G.Paun, G.Rozenberg, A.Salomaa, 10.1090/dimacs/048/22, In: Proc. 3rd DIMACS Workshop on DNA Based Computers, Philadelphia 1997, pp. 297-328. MR1688717DOI10.1090/dimacs/048/22
  6. Harrison, M. A., Ibarra, O. H., 10.1016/s0019-9958(68)90901-7, Inform. Control 13 (1968), 433-470. MR0238622DOI10.1016/s0019-9958(68)90901-7
  7. Hopcroft, J. E, Motwani, R., Ullman, J. D., Introduction to Automata Theory, Languages and Computation. Third edition., Prentice Hall 2007. MR0645539
  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., 10.1007/3-540-48321-7_34, Fundamentals of Computation Theory, Lecture Notes in Computer Science 1684 (1999), 409-420. MR1850250DOI10.1007/3-540-48321-7_34
  10. Paun, G., Rozenberg, G., Salomaa, A., 10.1007/978-3-662-03563-4, Springer-Verlag, Berlin, 1998. MR1724525DOI10.1007/978-3-662-03563-4
  11. Ray, K. S., Chatterjee, K., Ganguly, D., 10.1007/s11047-015-9494-5, Nat. Comput. 14 (2015), 691-699. MR3424746DOI10.1007/s11047-015-9494-5
  12. Samson, A. A., 10.1007/s11047-015-9494-5, Procedia - Social and Behavioral Sciences 195 (2015), 2037-2046. DOI10.1007/s11047-015-9494-5

NotesEmbed ?

top

You must be logged in to post comments.