Complexity of Promise Problems on Classical and Quantum Automata
From MaRDI portal
Publication:2944886
DOI10.1007/978-3-319-13350-8_12zbMath1323.68338OpenAlexW206812929MaRDI QIDQ2944886
Carlo Mereghetti, Beatrice Palano, Maria Paola Bianchi
Publication date: 8 September 2015
Published in: Computing with New Resources (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-13350-8_12
Related Items
Unary probabilistic and quantum automata on promise problems, Boolean language operations on nondeterministic automata with a pushdown of constant height, Promise problems solved by quantum and classical finite automata, Quantum finite automata: advances on Bertoni's ideas, The descriptional power of queue automata of constant length, Descriptional complexity of iterated uniform finite-state transducers, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- State succinctness of two-way finite automata with quantum and classical states
- Superiority of exact quantum automata for promise problems
- Finite automata and unary languages
- Lower bounds on the size of sweeping automata
- Quantum automata and quantum grammars
- Two-way finite automata with quantum and classical states.
- Regular languages accepted by quantum automata
- Algebraic results on quantum automata
- Quantum automata for some multiperiodic languages
- Small size quantum automata recognizing some regular languages
- Some formal tools for analyzing quantum automata.
- Optimal Simulations between Unary Automata
- Potential of Quantum Finite Automata with Exact Acceptance
- Generalizations of the distributed Deutsch–Jozsa promise problem
- Behaviours of Unary Quantum Automata
- Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
- Characterizations of 1-Way Quantum Finite Automata
- One-Way Finite Automata with Quantum and Classical States
- Quantum finite automata with control language
- Lower Bounds for Generalized Quantum Finite Automata
- Normal forms for unary probabilistic automata
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Size Lower Bounds for Quantum Automata
- On the State Complexity of Semi-quantum Finite Automata
- Mathematical Foundations of Computer Science 2003
- Mathematical Foundations of Computer Science 2005
- Probabilistic automata
- Trace monoids with idempotent generators and measure-only quantum automata
