Geodesic
Watson-Crick pushdown automata
Kybernetika, Tome 53 (2017) no. 5, pp. 868-876
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2017-5-0868
Classification : 68Q10, 68Q45
Keywords: deterministic Watson–Crick automata; deterministic Watson–Crick pushdown automata; deterministic multi-head pushdown automata; context free languages 
@article{10_14736_kyb_2017_5_0868,
     author = {Chatterjee, Kingshuk and Ray, Kumar S.},
     title = {Watson-Crick pushdown automata},
     journal = {Kybernetika},
     pages = {868--876},
     year = {2017},
     volume = {53},
     number = {5},
     doi = {10.14736/kyb-2017-5-0868},
     mrnumber = {3750108},
     zbl = {06861629},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2017-5-0868/}
}
TY  - JOUR
AU  - Chatterjee, Kingshuk
AU  - Ray, Kumar S.
TI  - Watson-Crick pushdown automata
JO  - Kybernetika
PY  - 2017
SP  - 868
EP  - 876
VL  - 53
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2017-5-0868/
DO  - 10.14736/kyb-2017-5-0868
LA  - en
ID  - 10_14736_kyb_2017_5_0868
ER  - 
%0 Journal Article
%A Chatterjee, Kingshuk
%A Ray, Kumar S.
%T Watson-Crick pushdown automata
%J Kybernetika
%D 2017
%P 868-876
%V 53
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2017-5-0868/
%R 10.14736/kyb-2017-5-0868
%G en
%F 10_14736_kyb_2017_5_0868
Chatterjee, Kingshuk; Ray, Kumar S. Watson-Crick pushdown automata. Kybernetika, Tome 53 (2017) no. 5, pp. 868-876. doi: 10.14736/kyb-2017-5-0868

[1] Chatterjee, K., Ray, K. S: Reversible Watson-Crick automata. Acta Informatica 54 (2017), 5, 487-499. | DOI | MR

[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

[3] Czeizler, E., Czeizler, E.: A short survey on Watson-Crick automata. Bull. EATCS 88 (2006), 104-119. | MR

[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 | MR

[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 | MR

[6] Harrison, M. A., Ibarra, O. H.: Multi-head and multi-tape pushdown automata. Inform. Control 13 (1968), 433-470. | DOI | MR

[7] Hopcroft, J. E, Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation. Third edition. Prentice Hall 2007. | MR

[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 | MR

[10] Paun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer-Verlag, Berlin, 1998. | DOI | MR

[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 | MR

[12] Samson, A. A.: 2-head pushdown automata. Procedia - Social and Behavioral Sciences 195 (2015), 2037-2046. | DOI

Cité par Sources :