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

Descripción completa

Detalles Bibliográficos
Autor principal: Linton, M
Formato: Journal article
Lenguaje:English
Publicado: Elsevier 2023