We consider semigroup algorithmic problems in the wreath product $\mathbb{Z} \wr \mathbb{Z}$. Our paper focuses on two decision problems introduced by Choffrut and Karhum\"{a}ki (2005): the Identity Problem (does a semigroup contain the neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of $\mathbb{Z} \wr \mathbb{Z}$. We show that both problems are decidable. Our result complements the undecidability of the Semigroup Membership Problem (does a semigroup contain a given element?) in $\mathbb{Z} \wr \mathbb{Z}$ shown by Lohrey, Steinberg and Zetzsche (ICALP 2013), and contributes an important step towards solving semigroup algorithmic problems in general metabelian groups.
翻译:我们考虑 $\mathbb{Z} \wr \mathbb{Z}$ 中复合半群的算法问题。本文着重探讨由 Choffrut 和 Karhum\"{a}ki (2005) 提出的两个决策问题:同一性问题(一个半群是否包含中性元素?)和群问题(一个半群是否为群?)因为 $\mathbb{Z} \wr \mathbb{Z}$ 中生成的子半群,我们表明这两个问题是可决定的。我们的结果补充了 Lohrey,Steinberg 和 Zetzsche (ICALP 2013) 显示的 $\mathbb{Z} \wr \mathbb{Z}$ 中复合半群成员问题(半群是否包含给定元素?)的不可判定性问题,并为解决不规则交换群中的半群算法问题迈出重要一步。