Characterizations of 1-Way Quantum Finite Automata
From MaRDI portal
Publication:3149877
DOI10.1137/S0097539799353443zbMath1051.68062arXivquant-ph/9903014MaRDI QIDQ3149877
Alex Brodsky, Nicholas J. Pippenger
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/9903014
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (66)
One-Way Finite Automata with Quantum and Classical States ⋮ Characterizations of quantum automata ⋮ On the Size of One-way Quantum Finite Automata with Periodic Behaviors ⋮ Simulation methods for quantum walks on graphs applied to formal language recognition ⋮ Energy complexity of regular language recognition ⋮ Automata theory based on quantum logic: Some characterizations ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ From Quantum Query Complexity to State Complexity ⋮ State succinctness of two-way finite automata with quantum and classical states ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ Classically time-controlled quantum automata ⋮ Size lower bounds for quantum automata ⋮ On the Power of One-Way Automata with Quantum and Classical States ⋮ Exact results for accepting probabilities of quantum automata. ⋮ Energy complexity of computation ⋮ Learning quantum finite automata with queries ⋮ Mirrors and memory in quantum automata ⋮ Energy complexity of regular languages ⋮ Another approach to the equivalence of measure-many one-way quantum finite automata and its application ⋮ Quantum inductive inference by finite automata ⋮ Equivalence checking of quantum finite-state machines ⋮ Lower Bounds for Generalized Quantum Finite Automata ⋮ Exponentially more concise quantum recognition of non-RMM regular languages ⋮ One-way reversible and quantum finite automata with advice ⋮ GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA ⋮ Automata theory based on quantum logic: reversibilities and pushdown automata ⋮ On injectivity of quantum finite automata ⋮ On language varieties without Boolean operations ⋮ Quantum \(\omega\)-automata over infinite words and their relationships ⋮ Quantum Pushdown Automata with Garbage Tape ⋮ SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES ⋮ Quantum automata for some multiperiodic languages ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ On the complexity of minimizing probabilistic and quantum automata ⋮ More on quantum, stochastic, and pseudo stochastic languages with few states ⋮ Two-tape finite automata with quantum and classical states ⋮ Small size quantum automata recognizing some regular languages ⋮ Unbounded-error quantum computation with small space bounds ⋮ Some formal tools for analyzing quantum automata. ⋮ Hierarchy and equivalence of multi-letter quantum finite automata ⋮ A probabilistic model of computing with words ⋮ Quantum versus deterministic counter automata ⋮ Determination of equivalence between quantum sequential machines ⋮ Trace monoids with idempotent generators and measure-only quantum automata ⋮ Determining the equivalence for one-way quantum finite automata ⋮ Interference automata ⋮ Some algebraic properties of measure-once two-way quantum finite automata ⋮ How does adiabatic quantum computation fit into quantum automata theory? ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ An application of quantum finite automata to interactive proof systems ⋮ Efficient probability amplification in two-way quantum finite automata ⋮ On a class of languages recognizable by probabilistic reversible decide-and-halt automata ⋮ Languages Recognized with Unbounded Error by Quantum Finite Automata ⋮ Acceptance Ambiguity for Quantum Automata ⋮ Quantum Automata Theory – A Review ⋮ A note on quantum sequential machines ⋮ Characterizations of one-way general quantum finite automata ⋮ Multi-letter quantum finite automata: decidability of the equivalence and minimization of states ⋮ On relation between linear temporal logic and quantum finite automata ⋮ Quantum State Complexity of Formal Languages ⋮ Quantum finite automata with control language ⋮ Regular languages accepted by quantum automata ⋮ Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata ⋮ Characterization of tree automata based on quantum logic ⋮ On hybrid models of quantum finite automata ⋮ Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
This page was built for publication: Characterizations of 1-Way Quantum Finite Automata
