Exponentially more concise quantum recognition of non-RMM regular languages

DOI10.1016/j.jcss.2014.06.008zbMath1401.81039OpenAlexW2963315980WikidataQ59196627 ScholiaQ59196627MaRDI QIDQ473186

Paulo Mateus, Lvzhou Li, Amílcar Sernadas, Dao Wen Qiu

Publication date: 24 November 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.06.008

zbMATH Keywords

equivalencedeterministic finite automatadecidabilityregular languagesstate complexityquantum finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (9)

Lower bounds on the size of semi-quantum finite automata ⋮ Three Attacks on the Mediated Semi‐Quantum Key Distribution without Invoking Quantum Measurement ⋮ Learning quantum finite automata with queries ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ Quantum Markov chains: description of hybrid systems, decidability of equivalence, and model checking linear-time properties ⋮ Application of distributed semi-quantum computing model in phase estimation ⋮ Promise problems solved by quantum and classical finite automata ⋮ On the power of two-way multihead quantum finite automata ⋮ On hybrid models of quantum finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unbounded-error quantum computation with small space bounds
• On the complexity of minimizing probabilistic and quantum automata
• Characterizations of one-way general quantum finite automata
• Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
• An application of quantum finite automata to interactive proof systems
• Improved constructions of quantum automata
• Improved constructions of mixed state quantum automata
• Solving systems of polynomial inequalities in subexponential time
• Extending stochastic and quantum functions
• Quantum automata and quantum grammars
• Two-way finite automata with quantum and classical states.
• Hierarchy and equivalence of multi-letter quantum finite automata
• Algebraic results on quantum automata
• Quantum automata for some multiperiodic languages
• Small size quantum automata recognizing some regular languages
• Determining the equivalence for one-way quantum finite automata
• Topological automata
• Characterizations of 1-Way Quantum Finite Automata
• One-Way Finite Automata with Quantum and Classical States
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• Quantum finite automata with control language
• Various Aspects of Finite Quantum Automata
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• Multi-letter Reversible and Quantum Finite Automata
• Probabilistic automata
• Logical Reversibility of Computation
• ANALYSIS OF QUANTUM FUNCTIONS
• Algorithms in real algebraic geometry

This page was built for publication: Exponentially more concise quantum recognition of non-RMM regular languages