Abstract: 1-way quantum finite automata are deterministic and reversible in nature, which greatly reduces its accepting property. In fact the set of languages accepted by 1-way quantum finite automata is a proper subset of regular languages. In this paper we replace the tape head of 1-way quantum finite automata with DNA double strand and name the model Watson-Crick quantum finite automata. The non-injective complementarity relation of Watson-Crick automata introduces non-determinism in the quantum model. We show that this introduction of non-determinism increases the computational power of 1-way Quantum finite automata significantly. We establish that Watson-Crick quantum finite automata can accept all regular languages and that it also accepts some languages not accepted by any multihead deterministic finite automata. Exploiting the superposition property of quantum finite automata we show that Watson-Crick quantum finite automata accept the language L=ww where w belongs to {a,b}*.
Recommendations
Cites work
- k + 1 Heads Are Better than k
- scientific article; zbMATH DE number 1236223 (Why is no real title available?)
- scientific article; zbMATH DE number 1342112 (Why is no real title available?)
- On the descriptional complexity of Watson-Crick automata
- One-way reversible multi-head finite automata
- Quantum automata and quantum grammars
- Reversible Watson-Crick automata
Cited in
(6)- Modeling of RNA secondary structures using two-way quantum finite automata
- Reversible Watson-Crick automata
- scientific article; zbMATH DE number 1342112 (Why is no real title available?)
- Watson-Crick T0L Systems and Red-Green Register Machines
- Watson-Crick pushdown automata.
- Two-way nondeterministic finite automata with quantum and classical states and their limits
This page was built for publication: Watson-Crick quantum finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035008)
