Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages

DOI10.1007/978-3-540-69507-3_25zbMath1132.68039OpenAlexW104993865MaRDI QIDQ5448781

Mika Hirvensalo

Publication date: 7 March 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69507-3_25

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68) Automata and formal grammars in connection with logical questions (03D05)

Related Items (11)

Polynomially ambiguous probabilistic automata on restricted languages ⋮ Decision Questions for Probabilistic Automata on Small Alphabets ⋮ On injectivity of quantum finite automata ⋮ Hierarchy and equivalence of multi-letter quantum finite automata ⋮ Freeness properties of weighted and probabilistic automata over bounded languages ⋮ Determining the equivalence for one-way quantum finite automata ⋮ Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs. ⋮ Polynomially Ambiguous Probabilistic Automata on Restricted Languages ⋮ Acceptance Ambiguity for Quantum Automata ⋮ A note on quantum sequential machines ⋮ Multi-letter quantum finite automata: decidability of the equivalence and minimization of states

This page was built for publication: Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages