English

191 Pages

Downloading requires you to have access to the YouScribe library

__
Learn all about the services we offer
__

Description

Algorithmic aspects of ﬁnitesemigroup 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 ﬁnite.LIAFA, CNRS and University Paris VIIPart IWhat this tutorial is about?The aim of this tutorial is to present somealgorithms to compute ﬁnite 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 ﬁnite semigroupsSeveral questions should be answered:• How is the semigroup given? (transformationsemigroup, semigroup of matrices over some(semi)ring, ﬁnite 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 ...

Subjects

Informations

Published by | Immi |

Reads | 20 |

Language | English |

Report a problem