Algorithms for computing finite semigroups

The aim of this paper is to present algorithms to compute finite semigroups. The semigroup is given by a set of generators taken in a larger semigroup, called the “universe”. This universe can be for instance the semigroup of all functions, partial functions, or relations on the set <1,…,n>, or the semigroup of × n matrices with entries in a given finite semiring.The alogrithm produces simultaneously a presentation of the semigroup by generators and relations, a confluent rewriting system for this presentation and the Cayley graph of the semigroup. The elements of the semigroups are identified with the reduced words of the rewriting systems.We also give some efficient algorithms to compute the Green relations, the local subsemigroups and the syntactic quasi-order of subsets of the semigroup.