zbMATH — the first resource for mathematics

Graph groups are biautomatic. (English) Zbl 0812.20018
Author’s summary: Graph groups admit a (finite) presentation in which each relation is of the form \(xy = yx\) for generators \(x\) and \(y\). While the two extreme cases of graph groups, free groups and free abelian groups, have been previously shown to be bicombable (in fact, biautomatic), neither of the normal forms typically used for the combings generalize successfully to arbitrary graph groups. The normal forms presented in this paper which do yield results for arbitrary graph groups utilize the concept of a “commuting clique” of generators, and when these normal forms are applied to free abelian groups, they differ from the “usual” normal forms. As the set of normal forms is a regular language over the free monoid on the set of generators and their formal inverses, it follows that graph groups are biautomatic.

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F05 Generators, relations, and presentations of groups
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
20F34 Fundamental groups and their automorphisms (group-theoretic aspects)
57M07 Topological methods in group theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20F28 Automorphism groups of groups
20E05 Free nonabelian groups
Full Text: DOI
[1] Alonso, J.M., Combings of groups, (), 165-178 · Zbl 0763.57001
[2] Baumslag, G.; Gersten, S.M.; Shapiro, M.; Short, H., Automatic groups and amalgams, J. pure appl. algebra, 76, 229-316, (1991) · Zbl 0749.20006
[3] Cannon, J.W.; Epstein, D.B.A.; Holt, D.F.; Patterson, M.S.; Thurston, W.P., Word processing in groups, (1992), Jones and Bartlett
[4] Cartier, P.; Foata, D., Problèmes combinatoires de commutation et réarrangements, () · Zbl 0186.30101
[5] Droms, C., Subgroups of graph groups, J. algebra, 110, 519-522, (1987) · Zbl 0625.20026
[6] Gersten, S.M.; Short, H.B., Small cancellation theory and automatic groups, Invent. math., 102, 305-334, (1990) · Zbl 0714.20016
[7] S. Hermiller and J. Meier, Algorithms and Geometry for Graph Products of Groups, J. Algebra, to appear. · Zbl 0831.20032
[8] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[9] Lyndon, R.C.; Schupp, P.E., Combinatorial group theory, () · Zbl 0368.20023
[10] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial group theory: presentations of groups in terms of generators and relations, (1966), Dover New York · Zbl 0138.25604
[11] Newman, M.H.A., On theories with a combinatorial definition of ‘equivalence’, Ann. of math., 43, 223-243, (1943) · Zbl 0060.12501
[12] Servatius, H.; Droms, C.; Servatius, B., Surface subgroups of graph groups, Proc. amer. math. soc., 106, 573-578, (1989) · Zbl 0677.20023
[13] Short, H.B., Groups and combings, Unité de mathématiques pures et appliquées, (1990) · Zbl 0714.20016
[14] Squier, C.C., Word problems and a homological finiteness condition for monoids, J. pure appl. algebra, 49, 201-217, (1987) · Zbl 0648.20045
[15] Wrathall, C., The word problem for free partially commutative groups, J. symbolic comput., 6, 99-104, (1988) · Zbl 0655.20027
[16] Wrathall, C., The conjugacy problem for free partially commutative groups can be solved in linear time, (1988), UC Santa Barbara Preprint · Zbl 0655.20027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.