TY - JOUR
T1 - From automatic structures to automatic groups
AU - Kharlampovich, Olga
AU - Khoussainov, Bakhadyr
AU - Miasnikov, Alexei
PY - 2014
Y1 - 2014
N2 - In this paper we introduce the concept of a Cayley graph automatic group (CGA group or graph automatic group, for short) which generalizes the standard notion of an automatic group. Like the usual automatic groups graph automatic ones enjoy many nice properties: these groups are invariant under the change of generators, they are closed under direct and free products, certain types of amalgamated products, and finite extensions. Furthermore, the word problem in graph automatic groups is decidable in quadratic time. However, the class of graph automatic groups is much wider then the class of automatic groups. For example, we prove that all finitely generated 2-nilpotent groups and Baumslag-Solitar groups BS(1, n) are graph automatic, as well as many other metabelian groups.
AB - In this paper we introduce the concept of a Cayley graph automatic group (CGA group or graph automatic group, for short) which generalizes the standard notion of an automatic group. Like the usual automatic groups graph automatic ones enjoy many nice properties: these groups are invariant under the change of generators, they are closed under direct and free products, certain types of amalgamated products, and finite extensions. Furthermore, the word problem in graph automatic groups is decidable in quadratic time. However, the class of graph automatic groups is much wider then the class of automatic groups. For example, we prove that all finitely generated 2-nilpotent groups and Baumslag-Solitar groups BS(1, n) are graph automatic, as well as many other metabelian groups.
KW - Automatic groups
KW - Cayley graphs
KW - Nilpotent and metabelian groups
KW - Word problem
UR - http://www.scopus.com/inward/record.url?scp=84900459455&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84900459455&partnerID=8YFLogxK
U2 - 10.4171/GGD/221
DO - 10.4171/GGD/221
M3 - Article
AN - SCOPUS:84900459455
SN - 1661-7207
VL - 8
SP - 157
EP - 198
JO - Groups, Geometry, and Dynamics
JF - Groups, Geometry, and Dynamics
IS - 1
ER -