The RepOrc class

For computing small degree transformation representations of a finite semigroup or monoid.

This class is a helper for Sims1 calling the word_graph member function attempts to find a right congruence, represented as an WordGraph, of the semigroup or monoid defined by the presentation consisting of its presentation() and long_rules() with the following properties:

the transformation semigroup defined by the WordGraph has size target_size() ;
the number of nodes in the WordGraph is at least min_nodes() and at most max_nodes().

If no such WordGraph can be found, then an empty WordGraph is returned (with 0 nodes and 0 edges).

Contents

`RepOrc`	For computing small degree transformation representations of a finite semigroup or monoid.
`RepOrc.add_excluded_pair`(…)	Add a pair that must be excluded from every congruence.
`RepOrc.add_included_pair`(…)	Add a pair that should be included in every congruence.
`RepOrc.add_pruner`(…)	Add a pruner to the search tree.
`RepOrc.clear_excluded_pairs`(…)	Clear the set of excluded words.
`RepOrc.clear_included_pairs`(…)	Clear the set of included words.
`RepOrc.clear_long_rules`(…)	Clear the set of long rules.
`RepOrc.clear_pruners`(…)	Clear the set of pruners.
`RepOrc.excluded_pairs`(…)	Returns the set of pairs that must be excluded from every congruence.
`RepOrc.first_long_rule_position`(…)	Set the beginning of the long rules (position).
`RepOrc.idle_thread_restarts`(…)	Overloaded function.
`RepOrc.included_pairs`(…)	Returns the set of pairs that must be excluded from every congruence.
`RepOrc.init`(…)	Overloaded function.
`RepOrc.long_rule_length`(…)	Set the length of a long rule.
`RepOrc.long_rules`(…)	Get the long rules.
`RepOrc.max_nodes`(…)	Overloaded function.
`RepOrc.min_nodes`(…)	Overloaded function.
`RepOrc.number_of_long_rules`(…)	Returns the number of rules marked as long rules.
`RepOrc.number_of_threads`(…)	Overloaded function.
`RepOrc.presentation`(…)	Overloaded function.
`RepOrc.pruners`(…)	Get all active pruners of the search tree.
`RepOrc.stats`(…)	Get the current stats object.
`RepOrc.target_size`(…)	Overloaded function.
`RepOrc.word_graph`(…)	Get the word graph.

Full API

class RepOrc

__init__(self: RepOrc, word: type) → None

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

Keyword Arguments:

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

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

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:

RepOrc

Raises:

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

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

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:

RepOrc

Raises:

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

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

Add a pruner to the search tree.

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

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: RepOrc) → RepOrc

Clear the set of excluded words.

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

clear_included_pairs(self: RepOrc) → RepOrc

Clear the set of included words.

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

clear_long_rules(self: RepOrc) → RepOrc

Clear the set of long rules.

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

clear_pruners(self: RepOrc) → RepOrc

Clear the set of pruners.

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

excluded_pairs(self: RepOrc) → 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]]

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

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:

RepOrc

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).

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

Overloaded function.

idle_thread_restarts(self: RepOrc) → 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: RepOrc, val: int) → RepOrc

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:: RepOrc
Raises:: LibsemigroupsError – if the argument val is 0.

included_pairs(self: RepOrc) → 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(*args, **kwargs)

Overloaded function.

init(self: RepOrc) → RepOrc

Reinitialize an existing RepOrc object.

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

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

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

Reinitialize an existing RepOrc object.

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

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

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

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:: RepOrc

long_rules(self: RepOrc) → 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]]]

max_nodes(self: RepOrc, val: int) → RepOrc

Overloaded function.

max_nodes(self: RepOrc) → int

Get the current maximum number of nodes.

This function returns the current value for the maximum number of nodes in the WordGraph that we are seeking.

Returns:: A value of type int.
Return type:: int

max_nodes(self: RepOrc, val: int) → RepOrc

Set the maximum number of nodes.

This function sets the maximum number of nodes in the WordGraph that we are seeking.

Parameters:: val (int) – the maximum number of nodes
Returns:: The first argument self.
Return type:: RepOrc

min_nodes(self: RepOrc, val: int) → RepOrc

Overloaded function.

min_nodes(self: RepOrc) → int

Get the current minimum number of nodes.

This function returns the current value for the minimum number of nodes in the WordGraph that we are seeking.

Returns:: A value of type int.
Return type:: int

min_nodes(self: RepOrc, val: int) → RepOrc

Set the minimum number of nodes.

This function sets the minimal number of nodes in the WordGraph that we are seeking.

Parameters:: val (int) – the minimum number of nodes
Returns:: The first argument self.
Return type:: RepOrc

number_of_long_rules(self: RepOrc) → int

Returns the number of rules marked as long rules.

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

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

Overloaded function.

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

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:: RepOrc
Raises:: LibsemigroupsError – if the argument val is 0.

number_of_threads(self: RepOrc) → int

Get the number of threads.

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

presentation(*args, **kwargs)

Overloaded function.

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

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:

RepOrc

Raises:

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

presentation(self: RepOrc) → 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: RepOrc) → 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: RepOrc) → 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

target_size(self: RepOrc, val: int) → RepOrc

Overloaded function.

target_size(self: RepOrc) → int

Get the current target size.

This function returns the current value for the target size, i.e. the desired size of the transformation semigroup corresponding to the WordGraph returned by the function word_graph().

Returns:: A value of type int.
Return type:: int

target_size(self: RepOrc, val: int) → RepOrc

Set the target size.

This function sets the target size, i.e. the desired size of the transformation semigroup corresponding to the WordGraph returned by the function word_graph().

Parameters:: val (int) – the target size.
Returns:: The first argument self.
Return type:: RepOrc

word_graph(self: RepOrc) → WordGraph

Get the word graph.

This function attempts to find a right congruence, represented as an WordGraph, of the semigroup or monoid defined by the presentation consisting of its presentation() and :py:meth`~RepOrc.long_rules` with the following properties:

the transformation semigroup defined by the WordGraph has size target_size() ;
the number of nodes in the WordGraph is at least min_nodes() and at most max_nodes().

If no such WordGraph can be found, then an empty WordGraph is returned (with 0 nodes and 0 edges).

Returns:: A value of type WordGraph.
Return type:: WordGraph