Résumé : Le but de cet article est de présenter
des algorithmes pour le calcul des semigroupes finis. Les semigroupes sont
donnés par un ensemble de générateurs pris dans un
semigroupe plus grand, appelé l'univers. Il peut s'agir par exemple
du semigroupe de toutes les applications, de toutes les fonctions ou de
toutes les relations sur l'ensemble {1, .. n} ou encore le semigroupe des
matrices n x n à coefficients dans un semianneau fini. L'algorithme
produit simultanément une présentation du semigroupe par
générateurs et relations, un système de
réécriture confluent pour cette présentation et le
graphe de Cayley du semigroupe. Les éléments du semigroupe
sont identifiés aux mots réduits du système de
réécriture. On donne également des algorithmes
efficaces pour calculer les relations de Green, les semigroupes locaux et
le préordre syntactique d'une partie du semigroupe.
Abstract : 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 x n matrices with entries in a given
finite semiring. The algorithm 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
system. We also give some efficient algorithms to compute the Green
relations, the local subsemigroups and the syntactic quasi-order of subsets
of the semigroup.