Automatic monoids and change of generators

The main result of this paper establishes invariance under change of generators for automatic structures for monoids (a property that is well known to hold for automatic groups but fails for semigroups). This result is then applied to show that if a free product of two monoids is automatic, then so are both the free factors. Finally the difference between automatic structures, in terms of monoid generating sets and semigroup generating sets, is discussed.