The identity problem in the special affine group of \(\mathbb{Z}^2\) (Q6960753)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 8062473
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The identity problem in the special affine group of \(\mathbb{Z}^2\) |
scientific article; zbMATH DE number 8062473 |
Statements
The identity problem in the special affine group of \(\mathbb{Z}^2\) (English)
0 references
11 July 2025
0 references
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})\).
0 references
matrix semigroup
0 references
special affine group
0 references
identity problem
0 references
group problem
0 references
0 references
0 references
