Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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

Authors: Markus Lohrey and Benjamin Steinberg
Journal: Proc. Amer. Math. Soc. 138 (2010), 445-453
MSC (2000): Primary 20E06, 20F10
Published electronically: September 16, 2009
MathSciNet review: 2557162
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. M. Benois.
    Parties rationnelles du groupe libre.
    C. R. Acad. Sci. Paris, Sér. A-B, 269:1188-1190, 1969. MR 0265496 (42:405)
  • 3. M. Benois and J. Sakarovitch.
    On the complexity of some extended word problems defined by cancellation rules.
    Information Processing Letters, 23(6):281-287, 1986. MR 874449 (88d:68046)
  • 4. M. Kambites, P. V. Silva, and B. Steinberg.
    On the rational subset problem for groups.
    Journal of Algebra, 309(2):622-639, 2007. MR 2303197 (2008b:20038)
  • 5. I. Kapovich, R. Weidmann, and A. Miasnikov.
    Foldings, graphs of groups and the membership problem.
    International Journal of Algebra and Computation, 15(1):95-128, 2005. MR 2130178 (2005m:20081)
  • 6. M. Lohrey and B. Steinberg.
    The submonoid and rational subset membership problems for graph groups.
    Journal of Algebra, 320(2):728-755, 2008. MR 2422314 (2009g:20064)
  • 7. 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.
  • 8. K. A. Mihaĭlova.
    The occurrence problem for free products of groups.
    Doklady Akademii Nauk SSSR, 127:746-748, 1959. MR 0106940 (21:5670)
  • 9. K. A. Mihaĭlova.
    The occurrence problem for direct products of groups.
    Math. USSR Sbornik (N.S.), 70(112):241-251, 1966.
    English translation. MR 0194497 (33:2707)
  • 10. E. Rips.
    Subgroups of small cancellation groups.
    Bulletin of the London Mathematical Society, 14:45-47, 1982. MR 642423 (83c:20049)
  • 11. N. S. Romanovskiĭ.
    Some algorithmic problems for solvable groups.
    Algebra i Logika, 13(1):26-34, 1973. MR 0357624 (50:10092)
  • 12. N. S. Romanovskiĭ.
    The embedding problem for abelian-by-nilpotent groups.
    Sibirsk. Mat. Zh., 21:170-174, 1980. MR 569186 (82c:20069)
  • 13. B. Schein.
    Semigroups of strong subsets.
    Volzhsky Matematichesky, 4:180-186, 1966. MR 0217198 (36:289)
  • 14. J.-P. Serre.
    Springer-Verlag, 2003. MR 1954121 (2003m:20032)
  • 15. J. R. Stallings.
    Topology of finite graphs.
    Invent. Math., 71(3):551-565, 1983. MR 695906 (85m:05037a)
  • 16. U. U. Umirbaev.
    The occurrence problem for free solvable groups.
    SibirskiĭFond Algebry i Logiki. Algebra i Logika, 34(2):211-232, 243, 1995. MR 1362615 (96k:20063)
  • 17. D. T. Wise.
    A residually finite version of Rips's construction.
    Bulletin of the London Mathematical Society, 35(1):23-29, 2003. MR 1934427 (2003g:20047)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 20E06, 20F10

Retrieve articles in all journals with MSC (2000): 20E06, 20F10

Additional Information

Markus Lohrey
Affiliation: Institut für Informatik, Universität Leipzig, 04009 Leipzig, Germany

Benjamin Steinberg
Affiliation: School of Mathematics and Statistics, Carleton University, Ottawa, Ontario, Canada K1S 5B6

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
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society