An automata theoretic approach to the generalized word problem in graphs of groups

2009/05/27 by Markus Lohrey, Lohrey, Markus, Benjamin Steinberg +1
Computer Science · Mathematics · #20E06 #20F10 #Cellular Automata and Applications #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #math.GR #msc:20E06 #msc:20F10 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0905.4395

arxiv created 2009/05/27 · openalex publication_date 2009/05/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a simpler proof using automata theory of a recent result of Kapovich, Weidmann and Myasnikov according to which so-called benign graphs of groups preserve decidability of the generalized word problem. These include graphs of groups in which edge groups are polycyclic-by-finite and vertex groups are either locally quasiconvex hyperbolic or polycyclic-by-finite and so in particular chordal graph groups (right-angled Artin groups).

Related

• Compressed conjugacy and the word problem for outer automorphism groups of graph groups
• Polynomial-time word problems
• Compressed words and automorphisms in fully residually free groups
• Word problems and embedding-obstructions in cellular automata groups on groups
• The generalised word problem in hyperbolic and relatively hyperbolic\n groups