From automatic structures to automatic groups.

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Generalizations of solvable and nilpotent groups (20F19) Geometric group theory (20F65)

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 group 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 B(1,n) are graph automatic, as well as many other metabelian groups.

Review text

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.

Recommendations

Cites work

Cited in

(54)

This page was built for publication: From automatic structures to automatic groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2016098)