2023/01/23 by Ruiwen Dong, Dong, Ruiwen
Computer Science · #semigroups and automata theory #Rough Sets and Fuzzy Logic #Digital Image Processing Techniques
paper · pdf · doi:10.48550/arxiv.2301.09502
We consider semigroup algorithmic problems in the Special Affine group SA(2, ℤ) = ℤ2 \rtimes SL(2, ℤ), which is the group of affine transformations of the lattice ℤ2 that preserve orientation. Our paper focuses on two decision problems introduced by Choffrut and Karhumäki (2005): the Identity Problem (does a semigroup contain a neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of SA(2, ℤ). We show that both problems are decidable and NP-complete. Since SL(2, ℤ) ≤ SA(2, ℤ) ≤ SL(3, ℤ), our result extends that of Bell, Hirvensalo and Potapov (2017) on the NP-completeness of both problems in SL(2, ℤ), and contributes a first step towards the open problems in SL(3, ℤ).