The Identity Problem in subsemigroups of metabelian groups (Ruiwen Dong, Saarbrucken)

19.03.2024 10:30

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 whether 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. 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 a Positivstellensatz-type local-global principle.

Lieu

Bâtiment: Conseil Général 7-9

Room 1-05, Tuesday 19.03.2024, Séminaire "Groupes et Géométrie"

entrée libre