On injectivity of quantum finite automata

DOI10.1016/J.JCSS.2021.05.002MaRDI QIDQ2229947zbMATH OpenOpenAlexWikidataFDO

Authors Paul C. Bell, Mika Hirvensalo

Publication date 17 September 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.01471

zbMATH Keywords

quantum finite automataquaternionsundecidabilityPost's correspondence problemmatrix freeness

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Acceptance Ambiguity for Quantum Automata
• Decidable and Undecidable Problems about Quantum Automata
• scientific article; zbMATH DE number 6533717
• Characterizations of 1-Way Quantum Finite Automata
• Quantum finite automata and linear context-free languages: a decidable problem

Cites work

• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 3572058 (Why is no real title available?)
• scientific article; zbMATH DE number 1964689 (Why is no real title available?)
• scientific article; zbMATH DE number 1821768 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• A class of free rotation groups
• Acceptance Ambiguity for Quantum Automata
• Characterizations of 1-Way Quantum Finite Automata
• Decidable and Undecidable Problems about Quantum Automata
• Decision problems concerning thinness and slenderness of formal languages
• Decision problems for probabilistic finite automata on bounded languages
• Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• On the decidability of semigroup freeness.
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• Periodic and Infinite Traces in Matrix Semigroups
• Quantum automata and quantum grammars
• Reachability problems in quaternion matrix and rotation semigroups
• Scalar ambiguity and freeness in matrix semigroups over bounded languages
• Some decision problems on integer matrices
• The freeness problem over matrix semigroups and bounded languages
• Undecidability bounds for integer matrices using Claus instances
• Undecidable problems for probabilistic automata of fixed dimension
• Unsolvability in 3 × 3 Matrices
• Vector Ambiguity and Freeness Problems in SL(2, ℤ)

Cited in

(2)

• Pumping lemma for quantum automata
• Quantum \(\omega\)-automata over infinite words and their relationships

This page was built for publication: On injectivity of quantum finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229947)