The fully compressed subgroup membership problem

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 an...

Fuld beskrivelse

Bibliografiske detaljer
Hovedforfatter: Linton, M
Format: Journal article
Sprog:English
Udgivet: Elsevier 2023