From automatic structures to automatic groups

Olga Kharlampovich, Bakhadyr Khoussainov, Alexei Miasnikov

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)157-198
Number of pages42
JournalGroups, Geometry, and Dynamics
Volume8
Issue number1
DOIs
StatePublished - 2014

Keywords

  • Automatic groups
  • Cayley graphs
  • Nilpotent and metabelian groups
  • Word problem

Fingerprint

Dive into the research topics of 'From automatic structures to automatic groups'. Together they form a unique fingerprint.

Cite this