Geodesic
Watson-Crick pushdown automata
Kybernetika, Tome 53 (2017) no. 5, pp. 868-876

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {53},
     number = {5},
     year = {2017},
     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
PB  - mathdoc
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
%I mathdoc
%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

Cité par Sources :