Quantum automata and quantum grammars
From MaRDI portal
Publication:1566730
DOI10.1016/S0304-3975(98)00191-1zbMath0939.68037arXivquant-ph/9707031OpenAlexW2041518499WikidataQ60162831 ScholiaQ60162831MaRDI QIDQ1566730
James P. Crutchfield, Moore, Cristopher
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/9707031
Quantum computation (81P68) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Unnamed Item ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ Classically time-controlled quantum automata ⋮ Language recognition power and succinctness of affine automata ⋮ Optimality and complexity in measured quantum-state stochastic processes ⋮ Quaternionic quantum automata ⋮ On the Power of One-Way Automata with Quantum and Classical States ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Mirrors and memory in quantum automata ⋮ Lattice-valued general orthomodular automata ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Eilenberg's variety theorem without Boolean operations ⋮ Energy complexity of regular languages ⋮ GAPs for Shallow Implementation of Quantum Finite Automata ⋮ GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA ⋮ Affine Computation and Affine Automaton ⋮ 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 ⋮ On the power of two-way multihead quantum finite automata ⋮ Quantum State Complexity of Formal Languages ⋮ ON THE DECIDABILITY OF THE INTERSECTION PROBLEM FOR QUANTUM AUTOMATA AND CONTEXT-FREE LANGUAGES ⋮ Improved Constructions of Quantum Automata ⋮ Inverse problems in dynamic cognitive modeling ⋮ Unary probabilistic and quantum automata on promise problems ⋮ 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 ⋮ Complexity Bounds of Constant-Space Quantum Computation ⋮ On intuitionistic fuzzy context-free languages ⋮ Interval type-2 fuzzy automata and interval type-2 fuzzy grammar ⋮ Complementing two-way finite automata ⋮ Automata theory based on quantum logic: recognizability and accessibility ⋮ Energy complexity of regular language recognition ⋮ Spectral simplicity of apparent complexity. I. The nondiagonalizable metadynamics of prediction ⋮ Nondeterministic unitary OBDDs ⋮ Automata theory based on quantum logic: Some characterizations ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ Quantum Finite Automata: A Modern Introduction ⋮ From Quantum Query Complexity to State Complexity ⋮ State succinctness of two-way finite automata with quantum and classical states ⋮ Classical and Quantum Counter Automata on Promise Problems ⋮ Unnamed Item ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ Fuzzy grammar theory based on lattices ⋮ On quantum realisation of Boolean functions by the fingerprinting technique ⋮ Size lower bounds for quantum automata ⋮ Superiority of exact quantum automata for promise problems ⋮ Exact results for accepting probabilities of quantum automata. ⋮ Topology, formal languages and quantum information ⋮ On probabilistic and quantum reaction systems ⋮ Modeling of RNA secondary structures using two-way quantum finite automata ⋮ A theory of computation based on unsharp quantum logic: finite state automata and pushdown automata ⋮ On a Conjecture by Christian Choffrut ⋮ 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 ⋮ Computation in finitary stochastic and quantum processes ⋮ Automata theory based on quantum logic: reversibilities and pushdown automata ⋮ Quantum automata and algebraic groups ⋮ On injectivity of quantum finite automata ⋮ Computing power of Turing machines in the framework of unsharp quantum logic ⋮ 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 grammars ⋮ Promise problems solved by quantum and classical finite automata ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ On the complexity of minimizing probabilistic and quantum automata ⋮ Quantum Physics, Topology, Formal Languages, Computation: A Categorical View as Homage to David Hilbert ⋮ More on quantum, stochastic, and pseudo stochastic languages with few states ⋮ Quantum computation with write-only memory ⋮ Two-tape finite automata with quantum and classical states ⋮ Computing spin networks ⋮ JUMPING FINITE AUTOMATA ⋮ 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 ⋮ Computation in Sofic Quantum Dynamical Systems ⋮ A Bialgebraic Approach to Automata and Formal Language Theory ⋮ Finite state and finite stop quantum languages ⋮ Periodic generalized automata over the reals ⋮ Watson-Crick quantum finite automata ⋮ Interactive proofs with quantum finite automata ⋮ Determining the equivalence for one-way quantum finite automata ⋮ Interference automata ⋮ Some algebraic properties of measure-once two-way quantum finite automata ⋮ Weakly regular quantum grammars and asynchronous quantum automata ⋮ An application of quantum finite automata to interactive proof systems ⋮ Improved constructions of quantum automata ⋮ Efficient probability amplification in two-way quantum finite automata ⋮ On a class of languages recognizable by probabilistic reversible decide-and-halt automata ⋮ Mathematical logic and quantum finite state automata ⋮ Language Recognition Power and Succinctness of Affine Automata ⋮ Languages Recognized with Unbounded Error by Quantum Finite Automata ⋮ An Algebra of Automata That Includes Both Classical and Quantum Entities ⋮ Acceptance Ambiguity for Quantum Automata ⋮ Quantum Automata Theory – A Review ⋮ Looking for Pairs that Hard to Separate: A Quantum Approach ⋮ A note on quantum sequential machines ⋮ Characterizations of one-way general quantum finite automata ⋮ On Hadamard square roots of unity ⋮ Multi-letter quantum finite automata: decidability of the equivalence and minimization of states ⋮ Universal Neural Field Computation ⋮ On coverings of products of uninitialized sequential quantum machines ⋮ On relation between linear temporal logic and quantum finite automata ⋮ A theory of computation based on quantum logic. I ⋮ Quantum finite automata with control language ⋮ Computing with quanta -- impacts of quantum theory on computation. ⋮ Two-way finite automata with quantum and classical states. ⋮ Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata ⋮ On the computational power of probabilistic and quantum branching program ⋮ The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Quantum mechanical Hamiltonian models of Turing machines
- Analytic models and ambiguity of context-free languages
- Dynamical recognizers: real-time language recognition by analog computers
- QRT FIFO automata, breadth-first grammars and their relations
- Analog computation via neural networks
- The calculi of emergence: Computation, dynamics and induction
- Bulk Spin-Resonance Quantum Computation
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Unpredictability and undecidability in dynamical systems
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- The evolution of emergent computation.
- Real-Time Definable Languages
- Probabilistic automata
- On stochastic languages
