The Identity Problem in ℤ \wr ℤ is decidable

2023/02/12 by Dong, Ruiwen
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2302.05939

Abstract

We consider semigroup algorithmic problems in the wreath product ℤ \wr ℤ. 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 ℤ \wr ℤ. 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 ℤ \wr ℤ shown by Lohrey, Steinberg and Zetzsche (ICALP 2013), and contributes an important step towards solving semigroup algorithmic problems in general metabelian groups.

Related

• Semigroup algorithmic problems in metabelian groups
• The Identity Problem in the special affine group of ℤ²
• Recent advances in algorithmic problems for semigroups
• On the decidability of semigroup freeness
• Semigroup Identities, Proofs, and Artificial Intelligence