Algorithms for computing finite semigroups

Véronique FROIDURE and Jean-Eric PIN

IBP-Litp 1996/37: Rapport de Recherche Litp / Litp research reports
18 pages - Décembre/December 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Algorithms for computing finite semigroups

Résumé : Le but de cet article est de présenter des algorithmes de calcul pour les semigroupes finis. Les semigroupes sont donnés par un nesmble de générateurs pris dans un semigroupe plus large, appelé "l'univers". Cet univers peut être par exemple le semigroupe de toutes les applications, fonctions ou relations sur un ensemble fini, ou encore le semigroupe des matrices carrées de taille n à coefficients sans 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 s'identifient alors aux mots réduits de ce 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 a finite set, 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 semigroup 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 a subset of the semigroup.

Publications internes Litp 1996 / Litp research reports 1996