2021/10/19 by Linton, Marco
#20E05 #20F10 (Primary) #68Q45 (Secondary) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR)
paper · doi:10.48550/arxiv.2110.10055
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.