Computing finite index congruences of finitely presented semigroups and monoids
From MaRDI portal
Publication:6508802
arXiv2302.06295MaRDI QIDQ6508802
J. D. Mitchell, Maria Tsalakou, R. Cirpons, Marina Anagnostopoulou-Merkouri
Abstract: In this paper we describe two different algorithms for computing the congruences of a finite semigroup or monoid, and compare these to existing algorithms and implementations. The first algorithm is a version of Sims' low index subgroup algorithm for finding the left or right congruences of a monoid. The second algorithm involves determining the distinct principal congruences, and then finding all of their possible joins. Variations of this algorithm have been suggested in numerous contexts by numerous authors. We show how to utilise the theory of relative Green's relations, and a version of Schreier's Lemma for monoids, to reduce the number of principal congruences that must be generated as the first step of this approach. Both of the algorithms described in this paper are implemented in the GAP package Semigroups, and the first algorithm is available in the C++ library libsemigroups and in its python bindings libsemigroups_pybind11.
Has companion code repository: https://github.com/libsemigroups/libsemigroups
This page was built for publication: Computing finite index congruences of finitely presented semigroups and monoids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508802)
