The subgroup membership problem for a group $G$ asks whether a given group element $g$ from $G$ belongs to a given finitely generated subgroup $H$ of $G$. Here, we are mainly interested in the case that $G$ is infinite, where the representation of elements of $G$ becomes relevant. In the case that $G$ is finitely generated, one can represent elements of $G$ by finite words over a generating set. But this representation is often not the most natural one. Consider for instance the group $GL(2,Z)$ of 2-dimensional integer matrices with determinant 1 or -1 (it is a finitely generated group). The most natural representation of an element of $GL(2,Z)$ is certainly a matrix with binary encoded integers. Concerning the subgroup membership problem, it is straightforward to show that it can be solved in polynomial time for $GL(2,Z)$ if elements of $GL(2,Z)$ are represented by finite words over a finite set of generators (the proof uses the fact that $GL(2,Z)$ is virtually-free. On the other hand, if elements of $GL(2,Z)$ are represented by matrices with binary encoded integers, the subgroup membership problem becomes more difficult. Nevertheless, we show that it can be solved in polynomial time. For the proof we extend Stallings folding procedure to graphs where edges are labelled with so called power words (finite words where binary encoded exponents are allowed).

Start Date

Venue

Online Zoom meeting

End Date

Markus Lohrey

Universität Siegen

Markus Lohrey-23Apr2021.pdf412.74 KB

Semigroups, Automata and Languages