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

Lohrey, Markus; Steinberg, Benjamin

doi:10.1090/S0002-9939-09-10126-0

An automata theoretic approach to the generalized word problem in graphs of groups
HTML articles powered by AMS MathViewer

by Markus Lohrey and Benjamin Steinberg PDF

Proc. Amer. Math. Soc. 138 (2010), 445-453 Request permission

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).

References

J. Avenhaus and D. Wißmann. Using rewriting techniques to solve the generalized word problem in polycyclic groups. In Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation, pages 322–337. ACM Press, 1989.
Michèle Benois, Parties rationnelles du groupe libre, C. R. Acad. Sci. Paris Sér. A-B 269 (1969), A1188–A1190. MR 265496
Michèle Benois and Jacques Sakarovitch, On the complexity of some extended word problems defined by cancellation rules, Inform. Process. Lett. 23 (1986), no. 6, 281–287. MR 874449, DOI 10.1016/0020-0190(86)90087-6
Mark Kambites, Pedro V. Silva, and Benjamin Steinberg, On the rational subset problem for groups, J. Algebra 309 (2007), no. 2, 622–639. MR 2303197, DOI 10.1016/j.jalgebra.2006.05.020
Ilya Kapovich, Richard Weidmann, and Alexei Miasnikov, Foldings, graphs of groups and the membership problem, Internat. J. Algebra Comput. 15 (2005), no. 1, 95–128. MR 2130178, DOI 10.1142/S021819670500213X
Markus Lohrey and Benjamin Steinberg, The submonoid and rational subset membership problems for graph groups, J. Algebra 320 (2008), no. 2, 728–755. MR 2422314, DOI 10.1016/j.jalgebra.2007.08.025
A. I. Malcev. On homomorphisms onto finite groups. American Mathematical Society Translations, Series 2, 119:67–79, 1983. Translation from Ivanov. Gos. Ped. Inst. Ucen. Zap. 18 (1958) 49–60.
K. A. Mihaĭlova, The occurrence problem for free products of groups, Dokl. Akad. Nauk SSSR 127 (1959), 746–748 (Russian). MR 0106940
K. A. Mihaĭlova, The occurrence problem for direct products of groups, Mat. Sb. (N.S.) 70 (112) (1966), 241–251 (Russian). MR 0194497
E. Rips, Subgroups of small cancellation groups, Bull. London Math. Soc. 14 (1982), no. 1, 45–47. MR 642423, DOI 10.1112/blms/14.1.45
N. S. Romanovskiĭ, Certain algorithmic problems for solvable groups, Algebra i Logika 13 (1973), 26–34, 121 (Russian). MR 0357624
N. S. Romanovskiĭ, The embedding problem for abelian-by-nilpotent groups, Sibirsk. Mat. Zh. 21 (1980), no. 2, 170–174, 239 (Russian). MR 569186
B. M. Šaĭn, Semigroups of strong subsets, Volž. Mat. Sb. vyp. 4 (1966), 180–186 (Russian). MR 0217198
Jean-Pierre Serre, Trees, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. Translated from the French original by John Stillwell; Corrected 2nd printing of the 1980 English translation. MR 1954121
John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551–565. MR 695906, DOI 10.1007/BF02095993
U. U. Umirbaev, The occurrence problem for free solvable groups, Algebra i Logika 34 (1995), no. 2, 211–232, 243 (Russian, with Russian summary); English transl., Algebra and Logic 34 (1995), no. 2, 112–124. MR 1362615, DOI 10.1007/BF00750164
Daniel T. Wise, A residually finite version of Rips’s construction, Bull. London Math. Soc. 35 (2003), no. 1, 23–29. MR 1934427, DOI 10.1112/S0024609302001406