Non-commutative integer programming
Time and place
4 PM on Friday, March 5th, 2010; GC 5417
Benjamin Steinberg (Carleton University, Ottawa)
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.
