The Sims1 class

For computing finite index right congruences of a finitely presented semigroup or monoid.

The algorithm implemented by this class is essentially the low index subgroup algorithm for finitely presented groups described in Section 5.6 of [Sim94]. The low index subgroups algorithm was adapted for semigroups and monoids by M. Anagnostopoulou-Merkouri, R. Cirpons, J. D. Mitchell, and M. Tsalakou; see [AMMT23].

The purpose of this class is to provide the functions iterator(), 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 iterator() yields WordGraph instances representing the action of the semigroup or monoid on the classes of a congruence.

See also

Sims2 for equivalent functionality for 2-sided congruences.

Contents

`Sims1`	For computing finite index right congruences of a finitely presented semigroup or monoid.
`Sims1.add_excluded_pair`(…)	Add a pair that must be excluded from every congruence.
`Sims1.add_included_pair`(…)	Add a pair that should be included in every congruence.
`Sims1.add_pruner`(…)	Add a pruner to the search tree.
`Sims1.clear_excluded_pairs`(…)	Clear the set of excluded words.
`Sims1.clear_included_pairs`(…)	Clear the set of included words.
`Sims1.clear_long_rules`(…)	Clear the set of long rules.
`Sims1.clear_pruners`(…)	Clear the set of pruners.
`Sims1.copy`(…)	Copy a `Sims1` object.
`Sims1.excluded_pairs`(…)	Returns the set of pairs that must be excluded from every congruence.
`Sims1.find_if`(…)	Apply a unary predicate to one-sided congruences with at most a given number of classes, until it returns `True`.
`Sims1.first_long_rule_position`(…)	Set the beginning of the long rules (position).
`Sims1.for_each`(…)	Apply a unary predicate to every one-sided congruence with at most a given number of classes.
`Sims1.idle_thread_restarts`(…)	Overloaded function.
`Sims1.included_pairs`(…)	Returns the set of pairs that must be excluded from every congruence.
`Sims1.init`(…)	Overloaded function.
`Sims1.iterator`(…)	Returns an iterator yielding all congruences of index at most n.
`Sims1.long_rule_length`(…)	Set the length of a long rule.
`Sims1.long_rules`(…)	Get the long rules.
`Sims1.number_of_congruences`(…)	Returns the number of one-sided congruences with up to a given number of classes.
`Sims1.number_of_long_rules`(…)	Returns the number of rules marked as long rules.
`Sims1.number_of_threads`(…)	Overloaded function.
`Sims1.presentation`(…)	Overloaded function.
`Sims1.pruners`(…)	Get all active pruners of the search tree.
`Sims1.stats`(…)	Get the current stats object.

Full API

class Sims1

__init__(*args, **kwargs)

Overloaded function.

__init__(self: Sims1, word: type) → None

This function returns an uninitialized Sims1 object that uses words of type specified by word.

Keyword Arguments:

word (type) – the type of words to use, must be list[int].

__init__(self: Sims1, p: Presentation) → None

Construct from a presentation.

The rules of the presentation p are used at every node in the depth first search conducted by an object of this type.

Parameters:

p (Presentation) – the presentation to construct from.

Raises:

LibsemigroupsError – if Presentation.throw_if_bad_alphabet_or_rules throws
LibsemigroupsError – if p has 0-generators and 0-relations.

See also

Sims1.presentation, Sims1.init

add_excluded_pair(self: Sims1, lhs: list[int], rhs: list[int]) → Sims1

Add a pair that must be excluded from every congruence.

Parameters:

lhs (list[int]) – the left hand side of the rule being added.
rhs (list[int]) – the right hand side of the rule being added.

Returns:

The first argument self.

Return type:

Sims1

Raises:

LibsemigroupsError – if Presentation.throw_if_letter_not_in_alphabet throws on lhs or rhs.

add_included_pair(self: Sims1, lhs: list[int], rhs: list[int]) → Sims1

Add a pair that should be included in every congruence.

Parameters:

lhs (list[int]) – the left hand side of the rule being added.
rhs (list[int]) – the right hand side of the rule being added.

Returns:

The first argument self.

Return type:

Sims1

Raises:

LibsemigroupsError – if Presentation.throw_if_letter_not_in_alphabet throws on lhs or rhs.

add_pruner(self: Sims1, pruner: collections.abc.Callable[[WordGraph], bool]) → Sims1

Add a pruner to the search tree.

Parameters:: pruner (collections.abc.Callable[[WordGraph], bool]) – a pruner function.
Returns:: The first argument self.
Return type:: Sims1

Warning

When running the Sims low-index backtrack with multiple threads, each added pruner must be guaranteed thread safe. Failing to do so could cause bad things to happen.

clear_excluded_pairs(self: Sims1) → Sims1

Clear the set of excluded words.

Returns:: The first argument self.
Return type:: Sims1

clear_included_pairs(self: Sims1) → Sims1

Clear the set of included words.

Returns:: The first argument self.
Return type:: Sims1

clear_long_rules(self: Sims1) → Sims1

Clear the set of long rules.

Returns:: The first argument self.
Return type:: Sims1

clear_pruners(self: Sims1) → Sims1

Clear the set of pruners.

Returns:: The first argument self.
Return type:: Sims1

copy(self: Sims1) → Sims1

Copy a Sims1 object.

Returns:: A copy.
Return type:: Sims1

excluded_pairs(self: Sims1) → list[list[int]]

Returns the set of pairs that must be excluded from every congruence.

This function returns the list of excluded pairs. The congruences computed by a Sims1 or Sims2 instance will never contain the relations of this presentation. In other words, the congruences computed by this instance are only taken among those that do not contain any of the pairs of elements of the underlying semigroup (defined by the presentation returned by presentation() and long_rules()) represented by the relations of the presentation returned by excluded_pairs().

Returns:: A list of words result such that (result[2*i], result[2*i+1]) is the i-th excluded pair.
Return type:: list[list[int]]

find_if(self: Sims1, n: int, pred: collections.abc.Callable[[WordGraph], bool]) → WordGraph

Apply a unary predicate to one-sided congruences with at most a given number of classes, until it returns True.

This function applies the predicate pred to every congruence with at most n classes, until a congruence satisfying the predicate is found. This function exists to:

provide some feedback on the progress of the computation if it runs for more than 1 second.
allow for searching for a congruence satisfying certain conditions using number_of_threads() in parallel.

Parameters:

n (int) – the maximum number of congruence classes.
pred (collections.abc.Callable[[WordGraph], bool]) – the predicate applied to every congruence found.

Returns:

The first WordGraph for which pred returns True, or the empty word graph if no such word graph exists.

Return type:

WordGraph

Raises:

LibsemigroupsError – if n is 0.
LibsemigroupsError – if presentation() has 0-generators and 0-relations (i.e. it has not been initialised).

See also

iterator(), for_each()

first_long_rule_position(self: Sims1, pos: int) → Sims1

Set the beginning of the long rules (position).

This function sets the beginning of the long rules using a position in self.presentation().rules. The “long rules” are the rules used after a complete deterministic word graph has been found in the search. If such a word graph is compatible with the long rules specified by this function, then this word graph is accepted, and if not it is rejected.

The purpose of this is to improve the backtrack search by reducing the time spent processing “long” rules in each node of the search tree, and to only check them at the leaves.

Parameters:

pos (int) – position of the the left hand side of the first long rule.

Returns:

The first argument self.

Return type:

Sims1

Raises:

LibsemigroupsError – if pos is not a valid position in self.presentation().rules.
LibsemigroupsError – if the rule at position pos is not the left hand side of a rule (i.e. if pos is odd).

for_each(self: Sims1, n: int, pred: collections.abc.Callable[[WordGraph], None]) → None

Apply a unary predicate to every one-sided congruence with at most a given number of classes.

This function applies the function pred to every one-sided congruence with at most n classes. This function exists to:

provide some feedback on the progress of the computation if it runs for more than 1 second.
allow for a function to be applied to all found word graphs using number_of_threads() in parallel.

Parameters:

n (int) – the maximum number of congruence classes.
pred (collections.abc.Callable[[WordGraph], None]) – the predicate applied to every congruence found.

Raises:

LibsemigroupsError – if n is 0.
LibsemigroupsError – if presentation() has 0-generators and 0-relations (i.e. it has not been initialised).

See also

iterator(), find_if()

idle_thread_restarts(self: Sims1, val: int) → Sims1

Overloaded function.

idle_thread_restarts(self: Sims1) → int

Get the idle thread restart attempt count.

This function returns the number of times an idle thread will attempt to restart before yielding during execution.

Returns:: The number of idle thread restarts.
Return type:: int

idle_thread_restarts(self: Sims1, val: int) → Sims1

Set the idle thread restart attempt count.

This function sets the idle thread restart attempt count. The default value is 64.

Parameters:: val (int) – the maximum number of times an idle thread will attempt to restart before yielding.
Returns:: The first argument self.
Return type:: Sims1
Raises:: LibsemigroupsError – if the argument val is 0.

included_pairs(self: Sims1) → list[list[int]]

Returns the set of pairs that must be excluded from every congruence.

This function returns the list of included pairs. The congruences computed by a Sims1 or Sims2 instance always contain the relations of this list. In other words, the congruences computed by this instance are only taken among those that contains the pairs of elements of the underlying semigroup (defined by the presentation returned by presentation() and long_rules()) represented by the relations of the list of words returned by included_pairs().

Returns:: A list of words result such that (result[2*i], result[2*i+1]) is the i-th included pair.
Return type:: list[list[int]]

init(self: Sims1, p: Presentation) → Sims1

Overloaded function.

init(self: Sims1) → Sims1

Reinitialize an existing Sims1 object.

This function puts a Sims1 object back into the same state as if it had been newly default constructed.

Returns:: The first argument self.
Return type:: Sims1

init(self: Sims1, that: Sims1) → Sims1

Reinitialize an existing Sims1 object.

This function re-initializes a Sims1 instance to be in the same state as that.

Parameters:: that (Sims1) – The instance use for reinitialization.
Returns:: The re-initialized object.
Return type:: Sims1

init(self: Sims1, p: Presentation) → Sims1

Reinitialize an existing Sims1 object from a presentation.

This function puts an object back into the same state as if it had been newly constructed from the presentation p.

Parameters:

p (Presentation) – the presentation.

Returns:

The first argument self.

Return type:

Sims1

Raises:

LibsemigroupsError – if Presentation.throw_if_bad_alphabet_or_rules throws
LibsemigroupsError – if p has 0-generators and 0-relations.

iterator(self: Sims1, n: int) → collections.abc.Iterator[WordGraph]

Returns an iterator yielding all congruences of index at most n.

This function returns an iterator yielding instances of WordGraph that represent the congruences with at most n classes. The order in which the congruences are yielded by the iterator is implementation specific. The meaning of the WordGraph objects yielded by the iterator depends on whether the input is a monoid presentation (i.e. 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 at most 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 at most 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 (int) – the maximum number of classes in a congruence.

Returns:

An iterator it yielding WordGraph objects with at most n or n + 1 nodes depending on the presentation, see above.

Return type:

collections.abc.Iterator[WordGraph]

Raises:

LibsemigroupsError – if n is 0.
LibsemigroupsError – if presentation() has 0-generators and 0-relations (i.e. it has not been initialised).

long_rule_length(self: Sims1, val: int) → Sims1

Set the length of a long rule.

Define the length of a “long” rule. This function modifies presentation() so that the rules whose length (sum of the lengths of both sides) is at least val (if any) occur at the end of presentation().rules and so that long_rules() returns all such rules. The relative orders of the rules within presentation() may not be preserved.

Parameters:: val (int) – the long rule length.
Returns:: The first argument self.
Return type:: Sims1

long_rules(self: Sims1) → collections.abc.Iterator[tuple[list[int], list[int]]]

Get the long rules.

Returns an iterator of long rules.

Returns:: An iterator.
Return type:: collections.abc.Iterator[tuple[list[int], list[int]]]

number_of_congruences(self: Sims1, n: int) → int

Returns the number of one-sided congruences with up to a given number of classes.

This function exists to:

provide some feedback on the progress of the computation if it runs for more than 1 second.
allow for the computation of the number of congruence to be performed using number_of_threads() in parallel.

Parameters:

n (int) – the maximum number of congruence classes.

Returns:

the number of one sided congruences with at most n congruence classes.

Return type:

int

Raises:

LibsemigroupsError – if n is 0.
LibsemigroupsError – if presentation() has 0-generators and 0-relations (i.e. it has not been initialised).

number_of_long_rules(self: Sims1) → int

Returns the number of rules marked as long rules.

Returns:: The number of long rules.
Return type:: int

number_of_threads(self: Sims1, val: int) → Sims1

Overloaded function.

number_of_threads(self: Sims1, val: int) → Sims1

Set the number of threads.

This function sets the number of threads to be used by Sims1 or Sims2. The default value is 1.

Parameters:: val (int) – the maximum number of threads to use.
Returns:: The first argument self.
Return type:: Sims1
Raises:: LibsemigroupsError – if the argument val is 0.

number_of_threads(self: Sims1) → int

Get the number of threads.

Returns:: The current maximum number of threads.
Return type:: int

presentation(*args, **kwargs)

Overloaded function.

presentation(self: Sims1, p: Presentation) → Sims1

Set the presentation over which the congruences produced by an instance are defined.

This function sets the presentation over which the congruences produced by an instance are defined. These are the rules used at every node in the depth first search conducted by objects of this type. The parameter p is always first converted to a Presentation of list[int] and it is this converted value that is used.

Parameters:

p (Presentation) – the presentation.

Returns:

The first argument self.

Return type:

Sims1

Raises:

LibsemigroupsError – if Presentation.throw_if_bad_alphabet_or_rules throws.
LibsemigroupsError – if p has 0-generators and 0-relations.

presentation(self: Sims1) → Presentation

Get the presentation over which the congruences produced by an instance are defined.

This function returns the defining presentation of a Sims1 or Sims2 instance. The congruences computed by Sims1.iterator of the appropriate subclass are defined over the semigroup or monoid defined by this presentation.

Returns:: The presentation.
Return type:: Presentation

pruners(self: Sims1) → list[collections.abc.Callable[[WordGraph], bool]]

Get all active pruners of the search tree.

This function returns a copy of the list of pruners. A pruner is any function that takes as input a word graph and returns a boolean. We require that if a pruner returns False for a word graph wg, then it returns False for all word graphs that are descended from wg in the Sims word graph search tree.

The pruners are used to refine the congruence search tree during the execution of the Sims algorithm. As such, the congruences computed by this instance are only taken among those whose word graphs are accepted by all pruners returned by pruners().

Returns:: A list of boolean functions on word graphs, the set of all pruners.
Return type:: list[collections.abc.Callable[[WordGraph], bool]]

stats(self: Sims1) → SimsStats

Get the current stats object.

This function returns the current stats object. The value returned by this function is a SimsStats object which contains some statistics related to the current Sims1 or Sims2 instance and any part of the depth first search already conducted.

Returns:: The SimsStats object containing the current stats.
Return type:: SimsStats