1. Watson-Crick pushdown automata
- Creator:
- Chatterjee , Kingshuk and Ray, Kumar S.
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- deterministic Watson-Crick automata, deterministic Watson-Crick pushdown automata, deterministic multi-head pushdown automata, and context free languages
- Language:
- English
- Description:
- 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.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public