The MinimalRepOrc class

For computing the minimal degree of a transformation representation arising from a right congruence 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, with the minimum possible number of nodes such that the action of the semigroup or monoid defined by the presentation consisting of its presentation() on the nodes of the WordGraph corresponds to a semigroup of size target_size().

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

Contents

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

Full API

class MinimalRepOrc

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

This function returns an uninitialized MinimalRepOrc 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: MinimalRepOrc, lhs: list[int], rhs: list[int]) → MinimalRepOrc

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:

MinimalRepOrc

Raises:

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

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

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:

MinimalRepOrc

Raises:

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

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

Add a pruner to the search tree.

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

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

Clear the set of excluded words.

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

clear_included_pairs(self: MinimalRepOrc) → MinimalRepOrc

Clear the set of included words.

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

clear_long_rules(self: MinimalRepOrc) → MinimalRepOrc

Clear the set of long rules.

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

clear_pruners(self: MinimalRepOrc) → MinimalRepOrc

Clear the set of pruners.

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

excluded_pairs(self: MinimalRepOrc) → 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: MinimalRepOrc, pos: int) → MinimalRepOrc

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:

MinimalRepOrc

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: MinimalRepOrc, val: int) → MinimalRepOrc

Overloaded function.

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

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

included_pairs(self: MinimalRepOrc) → 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: MinimalRepOrc) → MinimalRepOrc

Reinitialize an existing MinimalRepOrc object.

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

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

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

Reinitialize an existing MinimalRepOrc object.

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

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

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

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

long_rules(self: MinimalRepOrc) → 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_long_rules(self: MinimalRepOrc) → int

Returns the number of rules marked as long rules.

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

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

Overloaded function.

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

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

number_of_threads(self: MinimalRepOrc) → int

Get the number of threads.

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

presentation(*args, **kwargs)

Overloaded function.

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

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:

MinimalRepOrc

Raises:

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

presentation(self: MinimalRepOrc) → 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: MinimalRepOrc) → 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: MinimalRepOrc) → 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: MinimalRepOrc, val: int) → MinimalRepOrc

Overloaded function.

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

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

word_graph(self: MinimalRepOrc) → WordGraph

Get the word graph.

This function attempts to find a right congruence, represented as an WordGraph, with the minimum possible number of nodes such that the action of the semigroup or monoid defined by the presentation consisting of its presentation() and long_rules() on the nodes of the WordGraph corresponds to a semigroup of size target_size(). If no such WordGraph can be found, then an empty WordGraph is returned (with 0 nodes and 0 edges).

The algorithm implemented by this function repeatedly runs:

RepOrc(self)
    .min_nodes(1)
    .max_nodes(best)
    .target_size(self.target_size())
    .word_graph();

where best is initially target_size(), until the returned WordGraph is empty, and then the penultimate WordGraph is returned (if any).

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