On the Identity Problem for the Special Linear Group and the Heisenberg Group.

DOI10.4230/LIPIcs.ICALP.2018.132zbMath1499.20123arXiv1706.04166OpenAlexW2962913891MaRDI QIDQ5002819

Sang-Ki Ko, Igor Potapov, Reino Niskanen

Publication date: 28 July 2021

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

zbMATH Keywords

Heisenberg groupdecidabilityspecial linear groupmatrix semigroupidentity problem

Mathematics Subject Classification ID

Other matrix groups over rings (20H25) Decidability of theories and sets of sentences (03B25)

Related Items (3)

Reachability Problems for One-Dimensional Piecewise Affine Maps ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A PTIME solution to the restricted conjugacy problem in generalized Heisenberg groups
• Products of matrices and recursively enumerable sets
• A Kraft-McMillan inequality for free semigroups of upper-triangular matrices
• Knapsack problem for nilpotent groups
• A remark on the representation of trace monoids
• Reachability problems in quaternion matrix and rotation semigroups
• Subgroups of the braid group \(B_ 4\)
• The freeness problem over matrix semigroups and bounded languages
• Two-letter group codes that preserve aperiodicity of inverse finite automata.
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• Some Unexpected Consequences of Symmetry Computations
• Composition Problems for Braids
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
• On the Complexity of the Orbit Problem
• From classical theta functions to topological quantum field theory
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• On the complexity of integer programming
• Presentations for 3-Dimensional Special Linear Groups Over Integer Rings
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• The Identity Problem for Matrix Semigroups in SL₂(ℤ) is NP-complete
• Some decision problems on integer matrices
• On the Positivity Problem for Simple Linear Recurrence Sequences,
• Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
• Mathematical Foundations of Computer Science 2004
• On Termination of Integer Linear Loops
• Membership Problem for the Modular Group
• The orbit problem in higher dimensions
• Unsolvability in 3 × 3 Matrices
• Quantization and unitary representations
• Loop spaces, characteristic classes and geometric quantization

This page was built for publication: On the Identity Problem for the Special Linear Group and the Heisenberg Group.