The SimsRefinerFaithful class

For pruning the search tree when looking for congruences arising from right or two-sided congruences representing faithful actions.

This class provides a pruner for pruning the search tree when looking for right congruences representing faithful actions. A right congruence represents a faithful action if and only if it does not contain any non-trivial two-sided congruence. Equivalently, a word graph of a right congruence represents a faithful action if and only if there is no nontrivial pair of words \((u, v)\) such that every vertex of the word graph is compatible with \((u, v)\).

Contents

`SimsRefinerFaithful`	For pruning the search tree when looking for congruences arising from right or two-sided congruences representing faithful actions.
`SimsRefinerFaithful.__call__`(…)	Check if a word graph can be extended to one defining a faithful congruence.
`SimsRefinerFaithful.forbid`(…)	Get the forbidden pairs defining the refiner.
`SimsRefinerFaithful.init`(…)	Overloaded function.

Full API

class SimsRefinerFaithful

__init__(*args, **kwargs)

Overloaded function.

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

This function returns an uninitialized SimsRefinerFaithful 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: SimsRefinerFaithful, forbid: list[list[int]]) → None

Construct from set of forbidden pairs.

This function constructs a SimsRefinerFaithful pruner with respect to the set of forbidden relations in forbid. If forbid contains no trivial pairs (i.e. pairs of words that are equal in the underlying semigroup or monoid), then all word graphs rejected by SimsRefinerFaithful are guaranteed to not be extendable to a word graph representing a faithful congruence. Otherwise, the pruner will incorrectly reject all word graphs.

If in addition forbid is a set of relations containing all minimal congruence generating pairs of a given semigroup or monoid, then SimsRefinerFaithful will also correctly determine if a complete word graph represents a faithful congruence. Otherwise, the complete word graphs accepted by SimsRefinerFaithful are not guaranteed to be faithful and must be checked by some other means.

Parameters:: forbid (list[list[int]]) – A list of words such that (forbid[2*i], forbid[2*i+1]) is the i-th forbidden pair.

__call__(self: SimsRefinerFaithful, wg: WordGraph) → bool

Check if a word graph can be extended to one defining a faithful congruence.

Returns False if there is no way of adding edges and nodes to wg which will result in a word graph defining a faithful congruence. Otherwise returns True.

Parameters:: wg (WordGraph) – A word graph.
Returns:: A boolean.
Return type:: bool

forbid(self: SimsRefinerFaithful) → list[list[int]]

Get the forbidden pairs defining the refiner.

This function returns the defining forbidden pairs of a SimsRefinerFaithful instance.

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

init(self: SimsRefinerFaithful, forbid: list[list[int]]) → SimsRefinerFaithful

Overloaded function.

init(self: SimsRefinerFaithful) → SimsRefinerFaithful

Reinitialize an existing SimsRefinerFaithful object.

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

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

init(self: SimsRefinerFaithful, forbid: list[list[int]]) → SimsRefinerFaithful

Reinitialize an existing SimsRefinerFaithful object from a set of forbidden pairs.

This function puts an object back into the same state as if it had been newly constructed from set of forbidden pairs forbid.

Parameters:: forbid (list[list[int]]) – A list of words such that (forbid[2*i], forbid[2*i+1]) is the i-th forbidden pair.
Returns:: The first argument self.
Return type:: SimsRefinerFaithful