The Identity Problem in ℤ≀ℤ is decidable

02/12/2023

∙

by   Ruiwen Dong, et al.

∙

0

∙

share

We consider semigroup algorithmic problems in the wreath product ℤ≀ℤ. Our paper focuses on two decision problems introduced by Choffrut and Karhumä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 ℤ≀ℤ. 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 ℤ≀ℤ shown by Lohrey, Steinberg and Zetzsche (ICALP 2013), and contributes an important step towards solving semigroup algorithmic problems in general metabelian groups.