Quantum Pushdown Automata with Classical Stack and Tape Head |
Download PDF |
Jismy Joseph,K. S. Dersanambika. Quantum Pushdown Automata with Classical Stack and Tape Head. International Journal of Software and Informatics, 2014,8(3-4):309~316 |
Hits: 1606 |
Download times: 1340 |
|
|
Abstract:The quantum computational models were proposed to study how quantum mechanics influence the power of computing models. A lot of works are already done to extend simpler classical computational models to quantum models like quantum finite automata[3] and quantum pushdown automata[2,5]. Since the quantum part of a machine is not easy to implement, it is necessary to think about a computational model which minimize the quantum part of the model. Motivated by this fact in this paper we introduce a variation of quantum pushdown automata whose stack and tape head are implemented as classical devices. We observe that this model is powerful than classical pushdown automata
and some other quantum computational models. Here we also showed that it can recognize some non context free languages. |
keywords:quantum computational models 1QCFA QCPA QCPACT |
View Full Text View/Add Comment Download reader |