AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

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

Zoom

527 278 8807

passcode not visible

logged in users only

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.