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.
1
McGill University, Montreal, Canada
2
University of Auckland, New Zealand
3
Stevens Institute of Technology, Hoboken, USA
Olga Kharlampovich; Bakhadyr Khoussainov; Alexei Miasnikov. From automatic structures to automatic groups. Groups, geometry, and dynamics, Tome 8 (2014) no. 1, pp. 157-198. doi: 10.4171/ggd/221
@article{10_4171_ggd_221,
author = {Olga Kharlampovich and Bakhadyr Khoussainov and Alexei Miasnikov},
title = {From automatic structures to automatic groups},
journal = {Groups, geometry, and dynamics},
pages = {157--198},
year = {2014},
volume = {8},
number = {1},
doi = {10.4171/ggd/221},
url = {http://geodesic.mathdoc.fr/articles/10.4171/ggd/221/}
}
TY - JOUR
AU - Olga Kharlampovich
AU - Bakhadyr Khoussainov
AU - Alexei Miasnikov
TI - From automatic structures to automatic groups
JO - Groups, geometry, and dynamics
PY - 2014
SP - 157
EP - 198
VL - 8
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.4171/ggd/221/
DO - 10.4171/ggd/221
ID - 10_4171_ggd_221
ER -
%0 Journal Article
%A Olga Kharlampovich
%A Bakhadyr Khoussainov
%A Alexei Miasnikov
%T From automatic structures to automatic groups
%J Groups, geometry, and dynamics
%D 2014
%P 157-198
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4171/ggd/221/
%R 10.4171/ggd/221
%F 10_4171_ggd_221
