Characterizations of quantum automata
- Publication Type:
- Journal Article
- Theoretical Computer Science, 2004, 312 (2-3), pp. 479 - 489
- Issue Date:
We define q quantum finite automata (qQFAs) and q quantum regular grammars (qQRGs), and verify that they are exactly equivalent to those measure-once quantum finite automata (MO-QFAs) in the literature. In particular, we define q quantum pushdown automata (qQPDAs) and QPDAs that are at least as powerful as those defined by Moore and Crutchfield, and especially we focus on demonstrating the equivalence between qQPDAs and QPDAs. Also, we discuss some of the properties of languages accepted by qQPDAs; for example, every cut-point language accepted by qQPDA is independent of the cut-point. © 2003 Elsevier B.V. All rights reserved.
Please use this identifier to cite or link to this item: