The fully compressed subgroup membership problem

DOI10.1016/J.JALGEBRA.2023.03.026MaRDI QIDQ6038521zbMATH OpenOpenAlexFDO

Authors Marco Linton

Publication date 2 May 2023

Published in Journal of Algebra (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.10055

zbMATH Keywords

compressionfree groupsinvolutive automatamembership problemStallings foldingstraightline programs

Mathematics Subject Classification ID

Structure and classification of infinite or finite groups (20Exx) Special aspects of infinite or finite groups (20Fxx) Theory of computing (68Qxx)

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.

Cites work

• Algorithmics on SLP-compressed strings: a survey
• Compression techniques in group theory
• Efficient algorithms for Lempel-Ziv encoding
• scientific article; zbMATH DE number 1941341 (Why is no real title available?)
• scientific article; zbMATH DE number 1408351 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3339488 (Why is no real title available?)
• Membership Problem for the Modular Group
• Polynomial-time word problems.
• Processing Compressed Texts: A Tractability Border
• Stallings foldings and subgroups of free groups
• The complexity of compressed membership problems for finite automata
• The Nielsen reduction and P-complete problems in free groups
• The submonoid and rational subset membership problems for graph groups.
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Topology of finite graphs

Cited in

(2)

• Subgroups of free groups and primitive elements
• The Compressed Word Problem for Groups

This page was built for publication: The fully compressed subgroup membership problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038521)