Campus Event Calendar

Event Entry

What and Who

Decision problems in sub-semigroups of metabelian groups.

Ruiwen Dong
University of Oxford
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Friday, 9 June 2023
60 Minutes
E1 4


Algorithmic problems in metabelian groups have been studied as early as the 1950s since the work of Hall. In the 1970s Romanovskii proved decidability of the Group Membership problem (given the generators of a subgroup and a target element, decide if the target element is in the subgroup) in metabelian groups. However, Semigroup Membership (same as Group Membership, but with sub-semigroups) has been shown to be undecidable in several instances of metabelian groups using embeddings of either the Hilbert's tenth problem or two-counter automata.

In this talk we consider two "intermediate" decision problems: the Identity Problem (deciding if a sub-semigroup contains the neutral element) and the Group Problem (deciding if a sub-semigroup is a group). We reduce them to solving linear equations over the polynomial semiring N[X] and show decidability using an extension of a local-global principle by Einsiedler (2003).


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 06/06/2023 13:14
Roohani Sharma, 06/05/2023 18:39
Roohani Sharma, 06/02/2023 12:34 -- Created document.