Journal article
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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 468.9KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jalgebra.2023.03.026
Authors
Bibliographic Details
- Publisher:
- Elsevier
- Journal:
- Journal of Algebra More from this journal
- Volume:
- 628
- Pages:
- 562-583
- Publication date:
- 2023-08-01
- Acceptance date:
- 2023-03-30
- DOI:
- EISSN:
-
1090-266X
- ISSN:
-
0021-8693
Item Description
- Language:
-
English
- Keywords:
- Pubs id:
-
1339212
- Local pid:
-
pubs:1339212
- Deposit date:
-
2023-04-28
Terms of use
- Copyright holder:
- Crown Copyright
- Copyright date:
- 2023
- Rights statement:
- Crown Copyright © 2023 Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record