Cayley automata

The notion of a finite-state automaton is generalized to an automaton that scans as tapes arbitrary graphs preserving the properties of homogeneity and symmetry of ordinary Turing tapes. Cayley graph languages accepted by halting Cayley automata are syntactically characterized by quantifier-free formulas in the first-order theory of groups with parameters, the generators of the input Cayley graph. Also, the definite advantage of nondeterminism is established for Cayley automata on input graphs with at least two generators. © 1993