Uniform decision problems for automatic semigroups. (Q2509285)

The authors develop a suitable theoretical foundation for studying uniform decision problems for automatic semigroups. They present algorithms for deciding problems which include: Given an automatic structure, does the semigroup described have a zero or an identity? Is the semigroup right cancellative? etc. They also present algorithms for deciding whether an automatic semigroup is completely simple or completely zero-simple and, if it is, the algorithm computes a Rees matrix decomposition of the semigroup. The authors show, however, that the existence of right inverses for a given element of a given automatic semigroup is in general not decidable.