Prefer a chat interface with context about you and your work?
Decidable and Undecidable Problems about Quantum Automata
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 …