Deterministic and nondeterministic asynchronous automatic structures

Following the definition of asynchronous automatic structures in [3], we define non-deterministic asynchronous automatic structures and characterize these in terms of the asynchronous fellow traveller property. We show that any group with a non-deterministic asynchronous automatic structure has an asynchronous automatic structure. Non-deterministic asynchronous automatic structures are a labor saving method of showing that a group has an asynchronous automatic structure. They also allow one to define an equivalence relation on the class of non-deterministic asynchronous automatic structures which descends to the subclasses of deterministic asynchronous automatic structures and synchronous automatic structures.