6533b852fe1ef96bd12aab39

RESEARCH PRODUCT

Quantum Pushdown Automata

Marats Golovkins

subject

Discrete mathematicsNested wordComputer scienceDeterministic context-free grammarContext-free languagePushdown automatonNonlinear Sciences::Cellular Automata and Lattice GasesEmbedded pushdown automatonDeterministic pushdown automatonTuring machinesymbols.namesakeRegular languageDeterministic automatonProbabilistic automatonsymbolsQuantum finite automataAutomata theoryComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton

description

Quantum finite automata, as well as quantum pushdown automata were first introduced by C. Moore, J. P. Crutchfield [13]. In this paper we introduce the notion of quantum pushdown automata (QPA) in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [11]. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines [4]. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, two of them are not recognizable by deterministic pushdown automata and one seems to be not recognizable by probabilistic pushdown automata as well.

yearjournalcountryeditionlanguage
2000-01-01
https://doi.org/10.1007/3-540-44411-4_22