Algorithms for computing finite semigroups

Véronique Froidure et Jean-Éric Pin



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.

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!