On the complexity of minimizing probabilistic and quantum automata

DOI10.1016/J.IC.2012.07.002MaRDI QIDQ690502zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Paulo Mateus, Lvzhou Li, Daowen 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

minimizationprobabilistic automataquantum automatadecidability

Mathematics Subject Classification ID

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

Recommendations

• Stability and Complexity of Minimising Probabilistic Automata
• The complexity of probabilistic versus deterministic finite automata
• On the Complexity of Equivalence and Minimisation for Q-weighted Automata
• The complexity of probabilistic versus quantum finite automata
• Multi-letter quantum finite automata: decidability of the equivalence and minimization of states

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3694591 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• A note on quantum sequential machines
• Algorithms in real algebraic geometry
• Characterizations of 1-Way Quantum Finite Automata
• Characterizations of one-way general quantum finite automata
• Determining the equivalence for one-way quantum finite automata
• Probabilistic automata
• Quantum automata and quantum grammars
• Quantum theory, the Church–Turing principle and the universal quantum computer
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
• Unbounded-error quantum computation with small space bounds

Cited in

(17)

• scientific article; zbMATH DE number 7104930 (Why is no real title available?)
• On the Complexity of Equivalence and Minimisation for Q-weighted Automata
• Exponentially more concise quantum recognition of non-RMM regular languages
• Equivalence checking of quantum finite-state machines
• Matrix approach to simplification of finite state machines using semi-tensor product of matrices
• Promise problems solved by quantum and classical finite automata
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Quantum Büchi automata
• The quest for minimal quotients for probabilistic and Markov automata
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• On hybrid models of quantum finite automata
• The quest for minimal quotients for probabilistic 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
• Two-Way Quantum and Classical Automata with Advice for Online Minimization Problems
• scientific article; zbMATH DE number 4119632 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690502)