Semigroup Algorithmic Problems in Metabelian Groups

Abstract.

We consider semigroup algorithmic problems in finitely generated metabelian groups. Our paper focuses on three decision problems introduced by Choffrut and Karhumäki [ RAIRO Theor. Inform. Appl., 39 (2005), pp. 125–131]: the identity problem (does a semigroup contain a neutral element?), the group problem (is a semigroup a group?), and the inverse problem (does a semigroup contain the inverse of a generator?). We show that all three problems are decidable for finitely generated subsemigroups of finitely generated metabelian groups. In particular, we establish a correspondence between polynomial semirings and subsemigroups of metabelian groups using an interaction of graph theory, convex polytopes, algebraic geometry, and number theory. Since the semigroup membership problem (does a semigroup contain a given element?) is known to be undecidable in finitely generated metabelian groups, our result advances the decidability characterization of semigroup algorithmic problems in metabelian groups.