Decidable and undecidable problems about quantum automata
(2005) SIAM Journal on Computing — Vol. 34, n° 6, p. 1464-1473 (2005)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata, for which it is known that strict and nonstrict thresholds both lead to undecidable problems.
- Affiliations
Citations
Blondel, V., Jeandel, E., Koiran, P., & Portier, N. (2005). Decidable and undecidable problems about quantum automata. SIAM Journal on Computing, 34(6), 1464-1473. https://doi.org/10.1137/S0097539703425861 (Original work published 2005)