Stallings graphs for quasi-convex subgroups

Abstract

We show that one can define and effectively compute Stallings graphs for quasi-convex subgroups of automatic groups (\textit{e.g.} hyperbolic groups or right-angled Artin groups). These Stallings graphs are finite labeled graphs, which are canonically associated with the corresponding subgroups. We show that this notion of Stallings graphs allows a unified approach to many algorithmic problems: some which had already been solved like the generalized membership problem or the computation of a quasi-convexity constant (Kapovich, 1996); and others such as the computation of intersections, the conjugacy or the almost malnormality problems. Our results extend earlier algorithmic results for the more restricted class of virtually free groups. We also extend our construction to relatively quasi-convex subgroups of relatively hyperbolic groups, under certain additional conditions.

40 pages. New and improved version

References in corpus (3)

• Finite generating sets of relatively hyperbolic groups and applications to geodesic languages
• On definitions of relatively hyperbolic groups
• The membership problem for 3-manifold groups is solvable

Cited by in corpus (10)

• Quantifying separability in virtually special groups
• Statistics of subgroups of the modular group
• Folding-like techniques for CAT(0) cube complexes
• Core Surfaces
• Algorithms detecting stability and Morseness for finitely generated groups
• Random presentations and random subgroups: a survey
• A fast algorithm for Stallings foldings over virtually free groups
• Detecting conjugacy stability of subgroups in certain classes of groups
• Exponent equations in HNN-extensions
• Silhouettes and generic properties of subgroups of the modular group