Notions of automaticity in semigroups. (Q1402893)

The authors investigate the natural question of extending the notion of `automatic group' to `automatic semigroup'. They introduce four different definitions of automaticity in semigroups which are equivalent for groups. These four definitions arise when they consider which side (left or right) they choose for multiplication by generators and which side (left or right) they choose for padding pairs of strings of unequal length. The authors then demonstrate, via a sequence of examples, that their four definitions of automatic semigroup are truly independent. They further point out that there is some relationship between them in the cancellative monoid case. The authors also give properties of the four resulting classes of semigroups.