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
Additional Information
- Markus Lohrey
- Affiliation: Institut für Informatik, Universität Leipzig, 04009 Leipzig, Germany
- Email: lohrey@informatik.uni-leipzig.de
- Benjamin Steinberg
- Affiliation: School of Mathematics and Statistics, Carleton University, Ottawa, Ontario, Canada K1S 5B6
- MR Author ID: 633258
- Email: bsteinbg@math.carleton.ca
- Received by editor(s): May 27, 2009
- Published electronically: September 16, 2009
- Additional Notes: The authors would like to acknowledge the support of the DFG Mercator program. The second author is also supported by an NSERC grant.
- Communicated by: Jonathan I. Hall
- © Copyright 2009 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 138 (2010), 445-453
- MSC (2000): Primary 20E06, 20F10
- DOI: https://doi.org/10.1090/S0002-9939-09-10126-0
- MathSciNet review: 2557162