Computing finite index congruences of finitely presented semigroups and monoids
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916810171875328 |
|---|---|
| author | Anagnostopoulou-Merkouri, Marina Cirpons, Reinis Mitchell, James D. Tsalakou, Maria |
| author_facet | Anagnostopoulou-Merkouri, Marina Cirpons, Reinis Mitchell, James D. Tsalakou, Maria |
| contents | In this paper, we describe an algorithm for computing the left, right, or 2-sided congruences of a finitely presented semigroup or monoid with finitely many classes, and an alternative algorithm when the finitely presented semigroup or monoid is finite. We compare the two algorithms presented with existing algorithms and implementations. The first algorithm is a generalization of Sims' low-index subgroup algorithm for finding the 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 utilize 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_06295 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Computing finite index congruences of finitely presented semigroups and monoids Anagnostopoulou-Merkouri, Marina Cirpons, Reinis Mitchell, James D. Tsalakou, Maria Rings and Algebras Data Structures and Algorithms 20M20 In this paper, we describe an algorithm for computing the left, right, or 2-sided congruences of a finitely presented semigroup or monoid with finitely many classes, and an alternative algorithm when the finitely presented semigroup or monoid is finite. We compare the two algorithms presented with existing algorithms and implementations. The first algorithm is a generalization of Sims' low-index subgroup algorithm for finding the 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 utilize 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. |
| title | Computing finite index congruences of finitely presented semigroups and monoids |
| topic | Rings and Algebras Data Structures and Algorithms 20M20 |
| url | https://arxiv.org/abs/2302.06295 |