Algorithmic aspects of finite semigroup theory, a tutorial

Algorithmic aspects of finitesemigroup theory, a tutorial´Jean-Eric PinLIAFA, CNRS and University Paris 76, 8, 9 September 2006, St AndrewsLIAFA, CNRS and University Paris VIIOutline(1) What this tutorial is about?(2) Complexity(3) Presentation and Cayley graphs(4) Green’s relations(5) Idempotents, weak inverses and inverses(6) Blocks(7) Syntactic preorder(8) Other computationsWarning. In this tutorial, all semigroups are finite.LIAFA, CNRS and University Paris VIIPart IWhat this tutorial is about?The aim of this tutorial is to present somealgorithms to compute finite semigroups.Programming issues, like data structures,implementation or interface will not be addressed,but most algorithms are implemented in theC-programme semigroupe.This tutorial is addressed to mathematicians, not tocomputer scientists. For this reason, I will remind afew basic algorithms, when needed.LIAFA, CNRS and University Paris VIIComputing finite semigroupsSeveral questions should be answered:• How is the semigroup given? (transformationsemigroup, semigroup of matrices over some(semi)ring, finite presentation, ...)• What does one wish to compute?• What is the complexity of the algorithms?LIAFA, CNRS and University Paris VIIHow is the semigroup S given?I assume that S is a subsemigroup of a largersemigroup U (the universe), like:• the semigroup of all transformations on a set E,• the semigroup of n×n-Boolean matrices,• the semigroup of n×n-matrices with entries ...