The Identity Problem in the special affine group of \mathbb{Z}^2

arXiv2301.09502MaRDI QIDQ6424142FDOQ6424142

Authors:

Publication date: 23 January 2023

Abstract: We consider semigroup algorithmic problems in the Special Affine group

m a t h s f S A (2, m a t h b b Z) = m a t h b b Z^{2} t i m e s m a t h s f S L (2, m a t h b b Z)

, which is the group of affine transformations of the lattice

m a t h b b Z^{2}

that preserve orientation. Our paper focuses on two decision problems introduced by Choffrut and Karhum"{a}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

m a t h s f S A (2, m a t h b b Z)

. We show that both problems are decidable and NP-complete. Since

m a t h s f S L (2, m a t h b b Z) l e q m a t h s f S A (2, m a t h b b Z) l e q m a t h s f S L (3, m a t h b b Z)

, our result extends that of Bell, Hirvensalo and Potapov (SODA 2017) on the NP-completeness of both problems in

m a t h s f S L (2, m a t h b b Z)

, and contributes a first step towards the open problems in

m a t h s f S L (3, m a t h b b Z)

.

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 Q6424142)