Reachability problems in quaternion matrix and rotation semigroups

DOI10.1016/j.ic.2008.06.004zbMath1151.03021OpenAlexW1609583228MaRDI QIDQ958311

Igor Potapov, Paul C. Bell

Publication date: 3 December 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://dspace.lboro.ac.uk/2134/12044

zbMATH Keywords

undecidabilityquaternionsmembership problemmatrix semigroupsPost's correspondence problemrotation semigroups

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Undecidability and degrees of sets of sentences (03D35) Algebraic systems of matrices (15A30)

Related Items

Remarks concerning the freeness problem over morphism and matrix semigroups. ⋮ On the decidability of semigroup freeness ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ On injectivity of quantum finite automata ⋮ On the Identity Problem for the Special Linear Group and the Heisenberg Group. ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ Freeness Problem for Matrix Semigroups of Parikh Matrices ⋮ Weighted automata on infinite words in the context of attacker-defender games ⋮ Freeness properties of weighted and probabilistic automata over bounded languages ⋮ ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS ⋮ Relations in the semigroup of 2 × 2 upper-triangular matrices ⋮ Towards uniform online spherical tessellations ⋮ Acceptance Ambiguity for Quantum Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the membership of invertible diagonal and scalar matrices
• A class of free rotation groups
• Decision problems for semi-Thue systems with a few rules
• On Markov's undecidability theorem for integer matrices.
• On undecidability bounds for matrix decision problems
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• The numerical range of normal matrices with quaternion entries
• FREE GROUPS OF QUATERNIONS
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Decidable and Undecidable Problems about Quantum Automata
• Periodic and Infinite Traces in Matrix Semigroups
• Unsolvability in 3 × 3 Matrices
• Some Theorems On Matrices With Real Quaternion Elements
• Quaternions and matrices of quaternions