Defined in sims.hpp.
On this page we describe the functionality relating to the small index congruence algorithm for 1-sided congruences. The algorithm implemented by this class is essentially the low index subgroup algorithm for finitely presented groups described in Section 5.6 of Computation with Finitely Presented Groups by C. Sims; see [54]. The low index subgroups algorithm was adapted for semigroups and monoids by R. Cirpons, J. D. Mitchell, and M. Tsalakou; see [5]
The purpose of this class is to provide the functions cbegin, cend, for_each, and find_if which permit iterating through the one-sided congruences of a semigroup or monoid defined by a presentation containing (a possibly empty) set of pairs and with at most a given number of classes. An iterator returned by cbegin points at an WordGraph instance containing the action of the semigroup or monoid on the classes of a congruence.
- See also
- Sims2 for equivalent functionality for 2-sided congruences.
-
SimsSettings for the various things that can be set in a Sims1 object.
|
|
using | label_type = word_graph_type::label_type |
| | Type of the edge labels in the associated WordGraph objects.
|
| |
|
using | letter_type = word_type::value_type |
| | Type for letters in the underlying presentation.
|
| |
|
using | node_type = word_graph_type::node_type |
| | Type of the nodes in the associated WordGraph objects.
|
| |
|
using | size_type = word_graph_type::size_type |
| | The size_type of the associated WordGraph objects.
|
| |
|
using | word_graph_type = SimsBase::word_graph_type |
| | The type of the associated WordGraph objects.
|
| |
Returns a forward iterator pointing to the WordGraph representing the first congruence described by an object of this type with at most n classes.
If incremented, the iterator will point to the next such congruence. The order in which the congruences are returned is implementation specific. Iterators of the type returned by this function are equal whenever they point to equal objects. The iterator is exhausted if and only if it points to an WordGraph with zero nodes.
The meaning of the WordGraph pointed at by the returned iterator depends on whether the input is a monoid presentation (i.e. Presentation::contains_empty_word() returns true) or a semigroup presentation. If the input is a monoid presentation for a monoid \(M\), then the WordGraph pointed to by an iterator of this type has precisely n nodes, and the right action of \(M\) on the nodes of the word graph is isomorphic to the action of \(M\) on the classes of a right congruence.
If the input is a semigroup presentation for a semigroup \(S\), then the WordGraph has n + 1 nodes, and the right action of \(S\) on the nodes \(\{1, \ldots, n\}\) of the WordGraph is isomorphic to the action of \(S\) on the classes of a right congruence. It'd probably be better in this case if node \(0\) was not included in the output WordGraph, but it is required in the implementation of the low-index congruence algorithm, and to avoid unnecessary copies, we've left it in for the time being.
- Parameters
-
| n | the maximum number of classes in a congruence. |
- Returns
- An iterator
it of type iterator pointing to an WordGraph with at most n or n + 1 nodes.
- Exceptions
-
- Warning
- Copying iterators of this type is expensive. As a consequence, prefix incrementing
++it the returned iterator it significantly cheaper than postfix incrementing it++.
- See also
- cend
