On the complexity of minimizing probabilistic and quantum automata

DOI10.1016/j.ic.2012.07.002zbMath1279.68164OpenAlexW1997545301WikidataQ59196664 ScholiaQ59196664MaRDI QIDQ690502

Paulo Mateus, Lvzhou Li, Dao Wen Qiu

Publication date: 27 November 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.07.002

zbMATH Keywords

minimizationdecidabilityquantum automataprobabilistic automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

Unnamed Item ⋮ Equivalence checking of quantum finite-state machines ⋮ Exponentially more concise quantum recognition of non-RMM regular languages ⋮ Promise problems solved by quantum and classical finite automata ⋮ Categories of quantale-valued fuzzy automata: determinization and minimization ⋮ On the power of two-way multihead quantum finite automata ⋮ Multi-letter quantum finite automata: decidability of the equivalence and minimization of states ⋮ Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata ⋮ On hybrid models of quantum finite automata

Cites Work

• Unbounded-error quantum computation with small space bounds
• Characterizations of one-way general quantum finite automata
• A note on quantum sequential machines
• Quantum automata and quantum grammars
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
• Determining the equivalence for one-way quantum finite automata
• Characterizations of 1-Way Quantum Finite Automata
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Probabilistic automata
• Algorithms in real algebraic geometry
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of minimizing probabilistic and quantum automata