Acceptance Ambiguity for Quantum Automata

DOI10.4230/LIPIcs.MFCS.2019.70OpenAlexW2970404566MaRDI QIDQ5092433

Paul C. Bell, Mika Hirvensalo

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.70

zbMATH Keywords

undecidabilityquaternionsquantum finite automataPost's correspondence problemmatrix freeness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Mirrors and memory in quantum automata ⋮ On injectivity of quantum finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reachability problems in quaternion matrix and rotation semigroups
• Decision problems concerning thinness and slenderness of formal languages
• A class of free rotation groups
• Undecidable problems for probabilistic automata of fixed dimension
• Quantum automata and quantum grammars
• The freeness problem over matrix semigroups and bounded languages
• Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages
• On the decidability of semigroup freeness
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
• Characterizations of 1-Way Quantum Finite Automata
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Some decision problems on integer matrices
• Vector Ambiguity and Freeness Problems in SL(2, ℤ)
• Decision Problems for Probabilistic Finite Automata on Bounded Languages
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• Decidable and Undecidable Problems about Quantum Automata
• Periodic and Infinite Traces in Matrix Semigroups
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages
• Unsolvability in 3 × 3 Matrices
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS

This page was built for publication: Acceptance Ambiguity for Quantum Automata