Congruence¶

On this page we describe the functionality of the Congruence class. This class can be used for computing a congruence over a semigroup by running every applicable algorithm (and possibly some variants of the same algorithm) in parallel. This class is provided for convenience, at present it is not very customisable, and lacks some of the fine grained control offered by the classes implementing individual algorithms, such as ToddCoxeter and KnuthBendix.

See also

congruence_kind and tril.

>>> from libsemigroups_pybind11 import FpSemigroup, Congruence, congruence_kind
>>> S = FpSemigroup()
>>> S.set_alphabet(3)
>>> S.set_identity(0)
>>> S.add_rule([1, 2], [0])
>>> S.is_obviously_infinite()
True
>>> C = Congruence(congruence_kind.twosided, S)
>>> C.add_pair([1, 1, 1], [0])
>>> C.number_of_classes()
3

`Congruence`(args, *kwargs)	Overloaded function.
`Congruence.add_pair`(self, u, v)	Add a generating pair to the congruence.
`Congruence.class_index_to_word`(self, i)	If the congruence is defined over a semigroup with generators \(A\), then this function defines a injective function from \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes, to a fixed set of words over \(A\) representing distinct congruences classes.
`Congruence.const_contains`(self, u, v)	Check if a pair of words is known to belong to the congruence.
`Congruence.contains`(self, u, v)	Check if a pair of words belongs to the congruence.
`Congruence.dead`(self)	Check if the runner is dead.
`Congruence.finished`(self)	Check if the main algorithm, implemented in this class, has been run to completion or not.
`Congruence.generating_pairs`(self)	Returns an iterator pointing to the first generating pair of the congruence (if any).
`Congruence.has_parent_froidure_pin`(self)	Returns `True` if the congruence was created from a `FroidurePin` instance.
`Congruence.has_quotient_froidure_pin`(self)	Returns `True` if the congruence knows an isomorphic quotient semigroup represented by an instance of `FroidurePin`.
`Congruence.has_todd_coxeter`(self)	Checks if a `ToddCoxeter` instance is being used to compute the congruence.
`Congruence.is_quotient_obviously_finite`(self)	Return `True` if the number of classes in the congruence is obviously finite, and `False` if it is not obviously finite.
`Congruence.is_quotient_obviously_infinite`(self)	Return `True` if the number of classes in the congruence is obviously infinite, and `False` if it is not obviously infinite.
`Congruence.kill`(self)	Stop running the main algorithm(s) (thread-safe).
`Congruence.knuth_bendix`(self)	Returns the `KnuthBendix` being used to compute the congruence (if any).
`Congruence.less`(self, u, v)	This function returns `True` if the congruence class of `v` is less than the class of `v` in a total ordering of congruence classes.
`Congruence.non_trivial_classes`(self, i)	Returns the words belonging to non-trivial class with given index.
`Congruence.number_of_classes`(self)	Returns the number of classes in the congruence.
`Congruence.number_of_generating_pairs`(self)	Returns the number of generating pairs added by `add_pair()`.
`Congruence.number_of_non_trivial_classes`(self)	Returns the number of non-trivial classes (size > 1) of the congruence.
`Congruence.parent_froidure_pin`(self)	Returns the `FroidurePin` over which the congruence was defined, if it exists.
`Congruence.quotient_froidure_pin`(self)	Returns a semigroup represented as `FroidurePin` that is isomorphic to the quotient of the parent semigroup by the 2-sided congruence that this represents.
`Congruence.report`(self)	Check if it is time to report.
`Congruence.report_every`(self, t)	Set the minimum elapsed time between reports.
`Congruence.report_why_we_stopped`(self)	Report why we stopped.
`Congruence.run_for`(self, t)	Run for a specified amount of time.
`Congruence.run_until`(self, func)	Run until a nullary predicate returns `True` or `finished()`.
`Congruence.set_number_of_generators`(self, n)	Set the number of generators of the congruence.
`Congruence.stopped_by_predicate`(self)	Check if the main algorithm was, or should be, stopped by the nullary predicate passed as first argument to `run_until()`.
`Congruence.timed_out`(self)	Check if the main algorithm has or should timed out.
`Congruence.todd_coxeter`(self)	Returns the `ToddCoxeter` being used to compute the congruence (if any).
`Congruence.word_to_class_index`(self, w)	If the congruence, that an object of this type represents, is defined over a semigroup with generators \(A\), then this function defines a surjective function from the set of all words over \(A\) to either \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes.

class Congruence(*args, **kwargs)¶

Overloaded function.

__init__(self: _libsemigroups_pybind11.Congruence, kind: _libsemigroups_pybind11.congruence_kind) -> None
Construct from kind (left/right/2-sided) and options.

Constructs an empty instance of an interface to a congruence of type specified by the argument.
Parameters
kind (congruence_kind) the handedness of the congruence.
Complexity

Constant.
See also

set_number_of_generators() and add_pair().
__init__(self: _libsemigroups_pybind11.Congruence, kind: _libsemigroups_pybind11.congruence_kind, S: libsemigroups::FroidurePinBase) -> None
Construct from kind (left/right/2-sided) and FroidurePin.

Constructs a Congruence over the FroidurePin instance S representing a left/right/2-sided congruence according to kind.
Parameters
kind (congruence_kind) the handedness of the congruence.

S (FroidurePin) semigroup over which the congruence is defined.
Complexity

Linear in the size of S.
__init__(self: _libsemigroups_pybind11.Congruence, kind: _libsemigroups_pybind11.congruence_kind, S: libsemigroups::FpSemigroup) -> None
Construct from kind (left/right/2-sided) and FpSemigroup.

Constructs a Congruence over the FpSemigroup instance S representing a left/right/2-sided congruence according to type.
Parameters
kind (congruence_kind) the handedness of the congruence.

S (FpSemigroup) semigroup over which the congruence is defined.
Complexity

Constant.

add_pair(self: _libsemigroups_pybind11.Congruence, u: List[int], v: List[int]) → None¶

Add a generating pair to the congruence.

Parameters

u (List[int]) -- a word over the generators of the semigroup.
v (List[int]) -- a word over the generators of the semigroup.

Returns

(None)

class_index_to_word(self: _libsemigroups_pybind11.Congruence, i: int) → List[int]¶

If the congruence is defined over a semigroup with generators \(A\), then this function defines a injective function from \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes, to a fixed set of words over \(A\) representing distinct congruences classes.

Parameters: i (int) -- the index of the class whose representative we want to find
Returns: The word representing the i-th class of the congruence

const_contains(self: _libsemigroups_pybind11.Congruence, u: List[int], v: List[int]) → _libsemigroups_pybind11.tril¶

Check if a pair of words is known to belong to the congruence.

Parameters

u (List[int]) -- a word over the generators of the semigroup.
v (List[int]) -- a word over the generators of the semigroup.

Returns

tril.TRUE if the words u and v are known to belong to the same congruence class tril.FALSE if the words are known to not belong to the same congruence class tril.unknown otherwise.

contains(self: _libsemigroups_pybind11.Congruence, u: List[int], v: List[int]) → bool¶

Check if a pair of words belongs to the congruence.

Parameters

u (List[int]) -- a word over the generators of the semigroup.
v (List[int]) -- a word over the generators of the semigroup.

Returns

True if the words u and v belong to the same congruence class, and False otherwise.

dead(self: libsemigroups::Runner) → bool¶

Check if the runner is dead.

Parameters: None
Returns: A bool.

finished(self: _libsemigroups_pybind11.Congruence) → bool¶

Check if the main algorithm, implemented in this class, has been run to completion or not.

Parameters: None
Returns: A bool.

generating_pairs(self: _libsemigroups_pybind11.Congruence) → Iterator¶

Returns an iterator pointing to the first generating pair of the congruence (if any).

Parameters: None
Returns: An iterator.

has_knuth_bendix(self: _libsemigroups_pybind11.Congruence) → bool¶

Checks if a KnuthBendix instance is being used to compute the congruence.

Parameters: None
Returns: A bool.

has_parent_froidure_pin(self: libsemigroups::CongruenceInterface) → bool¶

Returns True if the congruence was created from a FroidurePin instance.

Parameters: None
Returns: A bool.

has_quotient_froidure_pin(self: libsemigroups::CongruenceInterface) → bool¶

Returns True if the congruence knows an isomorphic quotient semigroup represented by an instance of FroidurePin.

Parameters: None
Returns: A bool.

has_todd_coxeter(self: _libsemigroups_pybind11.Congruence) → bool¶

Checks if a ToddCoxeter instance is being used to compute the congruence.

Parameters: None
Returns: A bool.

is_quotient_obviously_finite(self: _libsemigroups_pybind11.Congruence) → bool¶

Return True if the number of classes in the congruence is obviously finite, and False if it is not obviously finite.

Parameters: None
Returns: A bool.

is_quotient_obviously_infinite(self: _libsemigroups_pybind11.Congruence) → bool¶

Return True if the number of classes in the congruence is obviously infinite, and False if it is not obviously infinite.

Parameters: None
Returns: A bool.

kill(self: libsemigroups::Runner) → None¶

Stop running the main algorithm(s) (thread-safe).

Parameters: None
Returns: (None).

kind(self: libsemigroups::CongruenceInterface) → _libsemigroups_pybind11.congruence_kind¶

Return if the congruence was created as a left, right, or two-sided congruence.

Parameters: None
Returns: A congruence_kind.

knuth_bendix(self: _libsemigroups_pybind11.Congruence) → libsemigroups::congruence::KnuthBendix¶

Returns the KnuthBendix being used to compute the congruence (if any).

Parameters: None
Returns: A KnuthBendix or None.

less(self: _libsemigroups_pybind11.Congruence, u: List[int], v: List[int]) → bool¶

This function returns True if the congruence class of v is less than the class of v in a total ordering of congruence classes.

Parameters

u (List[int]) -- a word over the generators of the semigroup.
v (List[int]) -- a word over the generators of the semigroup.

Returns

True if the class of u is less than that of v.

non_trivial_classes(self: _libsemigroups_pybind11.Congruence, i: int) → List[List[int]]¶

Returns the words belonging to non-trivial class with given index.

Parameters: i (int) -- the index of the non-trivial class.
Returns: A List[List[int]].

number_of_classes(self: _libsemigroups_pybind11.Congruence) → int¶

Returns the number of classes in the congruence.

Parameters: None
Returns: The number of congruences classes of this if this number is finite, or POSITIVE_INFINITY in some cases if this number is not finite.

number_of_generating_pairs(self: libsemigroups::CongruenceInterface) → int¶

Returns the number of generating pairs added by add_pair().

Returns: The number of generating pairs of the congruence that an object of this type represents.

number_of_generators(self: libsemigroups::CongruenceInterface) → int¶

Returns the number of generators specified by set_number_of_generators().

Parameters: None
Returns: The number of generators of the semigroup of the congruence, or UNDEFINED.

number_of_non_trivial_classes(self: _libsemigroups_pybind11.Congruence) → int¶

Returns the number of non-trivial classes (size > 1) of the congruence.

Parameters: None
Returns: The number of non-trivial classes of the congruence.

parent_froidure_pin(self: _libsemigroups_pybind11.Congruence) → libsemigroups::FroidurePinBase¶

Returns the FroidurePin over which the congruence was defined, if it exists.

Parameters: None
Returns: A FroidurePin.

quotient_froidure_pin(self: _libsemigroups_pybind11.Congruence) → libsemigroups::FroidurePinBase¶

Returns a semigroup represented as FroidurePin that is isomorphic to the quotient of the parent semigroup by the 2-sided congruence that this represents.

Parameters: None
Returns: A FroidurePin.

report(self: _libsemigroups_pybind11.Congruence) → bool¶

Check if it is time to report.

Parameters: None
Returns: A bool.

report_every(self: _libsemigroups_pybind11.Congruence, t: datetime.timedelta) → None¶

Set the minimum elapsed time between reports.

Parameters: t (datetime.timedelta) -- the amount of time between reports.
Returns: (None)

report_why_we_stopped(self: _libsemigroups_pybind11.Congruence) → None¶

Report why we stopped.

Parameters: None
Returns: (None)

run(self: _libsemigroups_pybind11.Congruence) → None¶

Run all the underlying algorithms to determine the structure of the congruence.

Parameters: None
Returns: (None)

run_for(self: _libsemigroups_pybind11.Congruence, t: datetime.timedelta) → None¶

Run for a specified amount of time.

Parameters: t (datetime.timedelta) -- the time to run for.
Returns: (None)

>>> from datetime import timedelta
>>> from libsemigroups_pybind11 import ToddCoxeter, congruence_kind
>>> tc = ToddCoxeter(congruence_kind.twosided)
>>> tc.set_number_of_generators(1)
>>> tc.add_pair([0] * 1000, [0] * 999)
>>> tc.run_for(timedelta(microseconds=10))

run_until(self: _libsemigroups_pybind11.Congruence, func: std::__1::function<bool ()>) → None¶

Run until a nullary predicate returns True or finished().

Parameters: func (Callable[], bool) -- a function.
Returns: (None)

set_number_of_generators(self: _libsemigroups_pybind11.Congruence, n: int) → None¶

Set the number of generators of the congruence.

Parameters: n (int) -- the number of generators.
Returns: (None)

stopped_by_predicate(self: _libsemigroups_pybind11.Congruence) → bool¶

Check if the main algorithm was, or should be, stopped by the nullary predicate passed as first argument to run_until().

Parameters: None
Returns: A bool.

timed_out(self: _libsemigroups_pybind11.Congruence) → bool¶

Check if the main algorithm has or should timed out.

Parameters: None
Returns: A bool.

todd_coxeter(self: _libsemigroups_pybind11.Congruence) → libsemigroups::congruence::ToddCoxeter¶

Returns the ToddCoxeter being used to compute the congruence (if any).

Parameters: None
Returns: A ToddCoxeter or None.

word_to_class_index(self: _libsemigroups_pybind11.Congruence, w: List[int]) → int¶

If the congruence, that an object of this type represents, is defined over a semigroup with generators \(A\), then this function defines a surjective function from the set of all words over \(A\) to either \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes.

Parameters: w (List[int]) -- the word whose class index we want to find.
Returns: The index of the congruence class corresponding to the word.