Characterizations of quantum automata

Publication Type:
Journal Article
Theoretical Computer Science, 2004, 312 (2-3), pp. 479 - 489
Issue Date:
Filename Description Size
Thumbnail2008004764OK.pdf223.51 kB
Adobe PDF
Full metadata record
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: