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.