The fully compressed subgroup membership problem

Abstract

Suppose that $F$ is a free group and $k$ is a natural number. We show that the fully compressed membership problem for $k$-generated subgroups of $F$ is solvable in polynomial time. In order to do this, we adapt the theory of Stallings' foldings to handle edges with compressed labels. This partially answers a question of Markus Lohrey.

arXiv comment11 pages, 2 figures