The identity problem in the special affine group of Z^2
The paper focuses on two decision problems: the identity problem (does a semigroup contain a neutral element?) and the group problem (is a semigroup a group?) for finitely generated subsemigroups of \(\mathrm{SA}(2, \mathbb{Z})\). The author shows that both problems are decidable and NP-complete.\N\NSince \(\mathrm{SL}(2, \mathbb{Z}) \leq \mathrm{SA}(2, \mathbb{Z}) \leq \mathrm{SL}(3, \mathbb{Z})\), the result extends that by \textit{P. C. Bell} et al. [SODA 2017, 187--206 (2017; Zbl 1410.68139)] on the NP-completeness of both problems in \(\mathrm{SL}(2, \mathbb{Z})\), and contributes a first step towards the open problems in \(\mathrm{SL}(3, \mathbb{Z})\).
- \(\beta\)-expansions and symbolic dynamics
- Affine \(SL(2)\) conformal blocks from 4d gauge theories
- Affine extensions of integer vector addition systems with states
- Affine maps, Euclidean motions and quadrics
- Algorithms for matrix groups and the Tits alternative
- Classifying orbits of the affine group over the integers
- Decidable and Undecidable Problems about Quantum Automata
- Free subgroups in linear groups
- Geometric group theory. With an appendix by Bogdan Nica
- Groups of cohomological dimension one
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 871949 (Why is no real title available?)
- scientific article; zbMATH DE number 3257446 (Why is no real title available?)
- scientific article; zbMATH DE number 3056890 (Why is no real title available?)
- Invariant measure under the affine group over Z
- Nearly Optimal Algorithms for Canonical Matrix Forms
- On Reachability Problems for Low-Dimensional Matrix Semigroups
- On the Identity Problem for the Special Linear Group and the Heisenberg Group.
- On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
- Polynomial Invariants for Affine Programs
- Quantum automata and algebraic groups
- Rational subsets of Baumslag-Solitar groups
- Reachability in register machines with polynomial updates
- Reachability problems in nondeterministic polynomial maps on the integers
- Some decision problems on integer matrices
- Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
- The Affine Group of a Lie Group
- The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
- The identity problem in nilpotent groups of bounded class
- The structure of some subgroups of the modular group
- When are two elements of \(GL(2,\mathbb{Z}{})\) similar?
This page was built for publication: The identity problem in the special affine group of \(\mathbb{Z}^2\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6960753)
