|
An automata theoretic approach to the generalized word problem in graphs of groups
Author(s):
Markus
Lohrey;
Benjamin
Steinberg
Journal:
Proc. Amer. Math. Soc.
138
(2010),
445-453.
MSC (2000):
Primary 20E06, 20F10
Posted:
September 16, 2009
Retrieve article in:
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:
-
- 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.
Trees.
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
Email:
lohrey@informatik.uni-leipzig.de
Benjamin
Steinberg
Affiliation:
School of Mathematics and Statistics, Carleton University, Ottawa, Ontario, Canada K1S 5B6
Email:
bsteinbg@math.carleton.ca
DOI:
10.1090/S0002-9939-09-10126-0
PII:
S 0002-9939(09)10126-0
Received by editor(s):
May 27, 2009
Posted:
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 of article:
Copyright
2009,
American Mathematical Society
|
Comments: webmaster@ams.org