Benjamin Steinberg, Carleton University

abstract: 

The classical decision problem of integer programming seeks to algorithmically determine whether an integral matrix equation $Ax=b$ has a non-negative solution $x$. It is well known that this problem is NP-complete. From an algebraic point of view, we are asking whether $b$ belongs to the submonoid generated by the columns of $A$, i.e., we are asking to decide membership in finitely generated submonoids of abelian groups. Thus the membership problem for finitely generated submonoids of an arbitrary group can be viewed as a non-commutative analogue of integer programming. In this talk we present a survey on what is known about the submonoid membership problem and the related membership problem for rational subsets of groups (subsets recognized by finite automata). In particular, we consider right-angled Artin groups, two-dimensional lamplighter groups and free metabelian groups.

This is joint work with Markus Lohrey.