The Identity Problem in the special affine group of Z 2
The Identity Problem in the special affine group of Z 2
复制标题
Z 2 特殊仿射群中的同一性问题
DOI：
10.1109/lics56636.2023.10175768
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Dong R
中科院分区：
文献类型：
--
作者：
Dong R
考虑特殊仿射群${\Text{SA}(2，{\mathbb{Z}})={{\mathbb{Z}}^2}次{\Text{SL}(2，{\mathbb{Z}})$的半群算法问题，它是保持定向的格的仿射变换群.本文主要研究Choffrut和Karhumäki(2005)提出的两个判定问题：单位问题(半群是否含有中立元？)以及群问题(半群是群吗？)对于有限生成的子半群。我们证明了这两个问题都是可判定的且是NP-完全的。因此，我们的结果推广了Bell，Hirvensalo和Potapov(Soda 2017)关于这两个问题的NP-完备性的结果，并且向文中的公开问题迈出了第一步。
We consider semigroup algorithmic problems in the Special Affine group ${\text{SA}}(2,{\mathbb{Z}}) = {{\mathbb{Z}}^2} \rtimes {\text{SL}}(2,{\mathbb{Z}})$, which is the group of affine transformations of the latticethat 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. We show that both problems are decidable and NP-complete. Since, our result extends that of Bell, Hirvensalo and Potapov (SODA 2017) on the NP-completeness of both problems in, and contributes a first step towards the open problems in.