Multi-letter quantum finite automata: decidability of the equivalence and minimization of states

DOI10.1007/s00236-011-0139-6zbMath1233.68154OpenAlexW2110196476WikidataQ59196668 ScholiaQ59196668MaRDI QIDQ766174

Lvzhou Li, Xiangfu Zou, Paulo Mateus, Jozef Gruska, Dao Wen Qiu

Publication date: 23 March 2012

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-011-0139-6

zbMATH Keywords

decidabilityquantum finite automataminimization of states

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)

Related Items (11)

From Quantum Query Complexity to State Complexity ⋮ QPSO-CD: quantum-behaved particle swarm optimization algorithm with Cauchy distribution ⋮ Learning quantum finite automata with queries ⋮ 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 ⋮ Periodic generalized automata over the reals ⋮ On the power of two-way multihead quantum finite automata ⋮ Characterizations of one-way general quantum finite automata ⋮ On coverings of products of uninitialized sequential quantum machines ⋮ 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
• Unnamed Item
• Unbounded-error quantum computation with small space bounds
• On the complexity of minimizing probabilistic and quantum automata
• A note on quantum sequential machines
• Quantum automata and quantum grammars
• Characterization of sequential quantum machines
• Hierarchy and equivalence of multi-letter quantum finite automata
• Determination of equivalence between quantum sequential machines
• Determining the equivalence for one-way quantum finite automata
• Topological automata
• Characterizations of 1-Way Quantum Finite Automata
• Languages Recognized with Unbounded Error by Quantum Finite Automata
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Multi-letter Reversible and Quantum Finite Automata
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages
• Probabilistic automata
• Algorithms in real algebraic geometry

This page was built for publication: Multi-letter quantum finite automata: decidability of the equivalence and minimization of states