1 Monoids and Semigroups

Semigroups and, even more, monoids are not far away from being like groups. But, surprisingly, they have not received much attention yet in the form of GAP programs. This small collection of files and manual chapters is an attempt to start closing this gap.

The only difference between a semigroup and a monoid is one element: the identity. Although this may lead to subtle differences in the behavior of these structures the underlying assumption of these programs is that you can always, by means of adding an element with the properties of an identity, turn a semigroup into a monoid. So most of the functions will only be available for monoids and not for semigroups. The actual process of adding an identity is also not supported at the moment.

The emphasis of this package is on transformation monoids (see chapter Transformation Monoids). However, it seemed to be a good idea to provide some of the framework for general monoids (this chapter) before concentrating on the special case. Separate chapters introduce transformations (see chapter Transformations) and binary relations (see chapter Binary Relations) as special types of monoid elements. Another chapter treats several ways of how a monoid can act on certain domains (see chapter Actions of Monoids).

For a general treatment of the theory of monoids and transformation monoids see~Lallement79 and Howie95. A detailed description of this implementation and the theory behind it is given in~LPRR1 and ~LPRR2.

A semigroup is constructed by the function SemiGroup (see SemiGroup) and a monoid is constructed by the function Monoid (see Monoid).

Note that monoid elements usually exist independently of a monoid, e.g., you can write down two transformations and compute their product without ever defining a monoid that contains them.

The chapter starts with a description of monoid elements, i.e. all those objects that can be element of a semigroup or of a monoid (see Comparisons of Monoid Elements, Operations for Monoid Elements, and IsMonoidElement). Then the functions which construct monoids and semigroups and the functions which test whether a given object is a monoid or a semigroup are described (see SemiGroup, IsSemiGroup, Monoid and IsMonoid).

Monoids and semigroups are domains, so every set theoretic function for domains is applicable to them (see Set Functions for Monoids). There are functions which construct Green Classes of various types as subsets of a monoid (see Green Classes, RClass, LClass, DClass and HClass), functions which test whether a given object is a Green class of a certain type (see IsRClass, IsLClass, IsDClass and IsHClass), and functions which determine the list of all Green Classes of some given type of a monoid (see RClasses, LClasses, DClasses and HClasses).

The next sections describe how set functions are applied to Green classes (see Set Functions for Green Classes) and how to compute various kinds of Schaccent127utzenberger groups (see SchutzenbergerGroup).

The final sections describe how to determine the idempotents of a monoid (see Idempotents), the lack of support for homomorphisms of monoids (see Monoid Homomorphisms) and how monoids are represented by records in GAP (see Monoid Records and Semigroup Records).

The functions described here are in the file "monoid.g".


  1. Comparisons of Monoid Elements
  2. Operations for Monoid Elements
  3. IsMonoidElement
  4. SemiGroup
  5. IsSemiGroup
  6. Monoid
  7. IsMonoid
  8. Set Functions for Monoids
  9. Green Classes
  10. RClass
  11. IsRClass
  12. RClasses
  13. LClass
  14. IsLClass
  15. LClasses
  16. DClass
  17. IsDClass
  18. DClasses
  19. PartialOrderDClasses
  20. HClass
  21. IsHClass
  22. HClasses
  23. Set Functions for Green Classes
  24. Green Class Records
  25. SchutzenbergerGroup
  26. Idempotents
  27. Monoid Homomorphisms
  28. Monoid Records and Semigroup Records
[Up] [Next] 

Version 2.4 (May 1998)