TY - JOUR
T1 - Stallings graphs for quasi-convex subgroups
AU - Kharlampovich, Olga
AU - Miasnikov, Alexei
AU - Weil, Pascal
N1 - Publisher Copyright:
© 2017 Elsevier Inc.
PY - 2017/10/15
Y1 - 2017/10/15
N2 - We show that one can define and effectively compute Stallings graphs for quasi-convex subgroups of automatic groups (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.
AB - We show that one can define and effectively compute Stallings graphs for quasi-convex subgroups of automatic groups (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.
KW - Algorithmic problems
KW - Group theory
KW - Hyperbolic and relatively hyperbolic groups
KW - Quasi-convex subgroups
UR - http://www.scopus.com/inward/record.url?scp=85025602029&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85025602029&partnerID=8YFLogxK
U2 - 10.1016/j.jalgebra.2017.05.037
DO - 10.1016/j.jalgebra.2017.05.037
M3 - Article
AN - SCOPUS:85025602029
SN - 0021-8693
VL - 488
SP - 442
EP - 483
JO - Journal of Algebra
JF - Journal of Algebra
ER -