On Reachability Problems for Low-Dimensional Matrix Semigroups

DOI10.4230/LIPIcs.ICALP.2019.44OpenAlexW2917070051MaRDI QIDQ5091195

Pavel Semukhin, Joël Ouaknine, Thomas Colcombet, James Worrell

Publication date: 21 July 2022

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

zbMATH Keywords

Heisenberg groupmembership problemgeneral linear groupmatrix semigroupshalf-space reachability problem

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (3)

Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two ⋮ On injectivity of quantum finite automata ⋮ Acceptance Ambiguity for Quantum Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On finite semigroups of matrices
• Algorithms for matrix groups and the Tits alternative
• Reachability problems in nondeterministic polynomial maps on the integers
• Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
• Quantum automata and algebraic groups
• Improved matrix pair undecidability results
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
• Polynomial-time algorithm for the orbit problem
• How to solve a quadratic equation in integers
• Decidability of the Membership Problem for 2 × 2 integer matrices
• The Identity Problem for Matrix Semigroups in SL₂(ℤ) is NP-complete
• Some decision problems on integer matrices
• On the integer solutions of quadratic equations
• Polynomial Invariants for Affine Programs
• Lie Groups, Lie Algebras, and Representations
• Decidable and Undecidable Problems about Quantum Automata
• Positivity Problems for Low-Order Linear Recurrence Sequences
• Membership Problem for the Modular Group
• Unsolvability in 3 × 3 Matrices

This page was built for publication: On Reachability Problems for Low-Dimensional Matrix Semigroups