Characterizations of quantum automata

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