On the complexity of minimizing probabilistic and quantum automata
DOI10.1016/J.IC.2012.07.002zbMATH Open1279.68164DBLPjournals/iandc/MateusQL12OpenAlexW1997545301WikidataQ59196664 ScholiaQ59196664MaRDI QIDQ690502FDOQ690502
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
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)
Cites Work
- Title not available (Why is that?)
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Title not available (Why is that?)
- Unbounded-error quantum computation with small space bounds
- Probabilistic automata
- Title not available (Why is that?)
- The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
- Title not available (Why is that?)
- Algorithms in real algebraic geometry
- Characterizations of one-way general quantum finite automata
- Title not available (Why is that?)
- A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
- Quantum automata and quantum grammars
- Determining the equivalence for one-way quantum finite automata
- Characterizations of 1-Way Quantum Finite Automata
- A note on quantum sequential machines
- Title not available (Why is that?)
Cited In (16)
- Title not available (Why is that?)
- 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
- Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
- The quest for minimal quotients for probabilistic and Markov automata
- On hybrid models of quantum 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
- Two-Way Quantum and Classical Automata with Advice for Online Minimization Problems
- Title not available (Why is that?)
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)
