From automatic structures to automatic groups. (Q2016098): Difference between revisions

The authors introduce the concept of a Cayley graph automatic group which generalizes the standard notion of an automatic group. Like the usual automatic groups the Cayley graph automatic groups enjoy many nice properties. In particular, the word problem in these groups is decidable in quadratic time. This class is much wider than the class of automatic groups. For example, all finitely generated nilpotent of class two groups and Baumslag-Solitar groups \(BS(1,n)\) are Cayley graph automatic.