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 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.

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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.