The Congruence class

Class for running Kambites, KnuthBendix, and ToddCoxeter in parallel.

On this page we describe the functionality relating to the class Congruence in libsemigroups. This class can be used for computing a congruence over a semigroup or monoid by running every applicable algorithm from libsemigroups (and 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 Kambites, KnuthBendix, and ToddCoxeter.

See also

Runner, congruence_kind, and tril.

Important

The class Congruence has all the methods of the Runner class but, for boring technical reasons, is not a subclass of Runner. If thing is an instance of Congruence, then you can use thing as if it were an instance of Runner but isinstance(thing, Runner) will return False.

>>> from libsemigroups_pybind11 import (Presentation, presentation, Congruence,
... congruence_kind, is_obviously_infinite)
>>> p = Presentation([0, 1])
>>> p.contains_empty_word(True)
<monoid presentation with 2 letters, 0 rules, and length 0>
>>> presentation.add_rule(p, [0, 1], [])
>>> cong = Congruence(congruence_kind.twosided, p)
>>> is_obviously_infinite(cong)
True
>>> cong.add_generating_pair([1, 1, 1], [])
<2-sided Congruence over <monoid presentation with 2 letters, 1 rule, and length 2> with 1 gen. pair, 4 runners>
>>> cong.number_of_classes()
3
>>> is_obviously_infinite(cong)
False

Contents

Congruence

Class for running Kambites, KnuthBendix, and ToddCoxeter in parallel.

Congruence.add_generating_pair(…)

Add a generating pair.

Congruence.contains(…)

Check containment of a pair of words.

Congruence.copy(…)

Copy a Congruence object.

Congruence.currently_contains(…)

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

Congruence.generating_pairs(…)

Get the generating pairs of the congruence.

Congruence.get(…)

Returns the t instance used to compute the congruence (if any).

Congruence.has(…)

Returns whether or not there is an instance of type t within the congruence.

Congruence.init(…)

Overloaded function.

Congruence.kind(…)

The kind of the congruence (1- or 2-sided).

Congruence.max_threads(…)

Overloaded function.

Congruence.number_of_classes(…)

Compute the number of classes in the congruence.

Congruence.number_of_generating_pairs(…)

Returns the number of generating pairs.

Congruence.number_of_runners(…)

Get the number of runners.

Congruence.presentation(…)

Get the presentation used to define a Congruence instance (if any).

Congruence.reduce(…)

Reduce a word.

Congruence.reduce_no_run(…)

Reduce a word.

Full API

class Congruence
__init__(*args, **kwargs)

Overloaded function.

__init__(word: type) → None

Default constructor.

This function default constructs an uninitialised Congruence instance.

Keyword Arguments:

  • word (type) – the type of words to use, must be either str or list[int]

__init__(self: Congruence, knd: congruence_kind, p: Presentation) → None

Construct from congruence_kind and Presentation.

This function constructs a Congruence instance representing a congruence of kind knd over the semigroup or monoid defined by the presentation p.

Parameters:
Raises:

LibsemigroupsError – if p is not valid.

add_generating_pair(self: Congruence, u: list[int] | str, v: list[int] | str) → Congruence

Add a generating pair.

This function adds a generating pair to the congruence represented by a Congruence instance.

Parameters:

  • u (list[int] | str) – the first item in the pair.

  • v (list[int] | str) – the second item in the pair.

Returns:

self.

Return type:

Congruence

Raises:
contains(self: Congruence, u: list[int] | str, v: list[int] | str) → bool

Check containment of a pair of words.

This function checks whether or not the words u and v are contained in the congruence represented by a Congruence instance.

Parameters:
Returns:

Whether or not the pair belongs to the congruence.

Return type:

bool

Raises:

LibsemigroupsError – if any of the values in u or v is out of range, i.e. they do not belong to presentation().alphabet() and Presentation.throw_if_letter_not_in_alphabet raises.

copy(self: Congruence) → Congruence

Copy a Congruence object.

Returns:

A copy.

Return type:

Congruence

currently_contains(self: Congruence, u: list[int] | str, v: list[int] | str) → tril

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

This function checks whether or not the words u and v are already known to be contained in the congruence represented by a Congruence instance. This function performs no enumeration, so it is possible for the words to be contained in the congruence, but that this is not currently known.

Parameters:
Returns:

Return type:

tril

Raises:

LibsemigroupsError – if any of the values in u or v is out of range, i.e. they do not belong to presentation().alphabet() and Presentation.throw_if_letter_not_in_alphabet raises.

generating_pairs(self: Congruence) → list[list[int] | str]

Get the generating pairs of the congruence.

This function returns the generating pairs of the congruence as added via Congruence.add_generating_pair.

Returns:

The list of generating pairs.

Return type:

list[list[int] | str]

get(self: Congruence, t: type) → Kambites | KnuthBendix | ToddCoxeter

Returns the t instance used to compute the congruence (if any).

This function returns (a copy of) the object of type t used to compute the congruence (if any). If there is no such object, then an exception is raised.

Parameters:

t (type) – The type of object being sought (must be Kambites, KnuthBendix, or ToddCoxeter).

Returns:

A copy of the instance of type t.

Return type:

Kambites | KnuthBendix | ToddCoxeter

Raises:

LibsemigroupsError – if there is no object of type t within self.

has(self: Congruence, t: type) → bool

Returns whether or not there is an instance of type t within the congruence.

This function returns True if self contains an instance of type t, and False if not.

Parameters:

t (type) – The type of object being sought (must be Kambites, KnuthBendix, or ToddCoxeter).

Returns:

Whether or not there is an object of type t in self.

Return type:

bool

init(*args, **kwargs)

Overloaded function.

init(self: Congruence) → Congruence

Re-initialize a Congruence instance.

This function puts a Congruence instance back into the state that it would have been in if it had just been newly default constructed.

Returns:

self.

Return type:

Congruence

init(self: Congruence, knd: congruence_kind, p: Presentation) → Congruence

Re-initialize a Congruence instance.

This function re-initializes a Congruence instance as if it had been newly constructed from knd and p.

Parameters:
Returns:

self.

Return type:

Congruence

Raises:

LibsemigroupsError – if p is not valid.

kind(self: Congruence | Kambites | KnuthBendix | ToddCoxeter) → congruence_kind

The kind of the congruence (1- or 2-sided).

This function returns the kind of the congruence represented by self. See congruence_kind for details.

Returns:

The kind of the congruence (1- or 2-sided).

Return type:

congruence_kind

Complexity:

Constant.

max_threads(*args, **kwargs)

Overloaded function.

max_threads(self: Congruence, val: int) → Congruence

Set the maximum number of threads.

Parameters:

val (int) – the number of threads.

Returns:

self.

Return type:

Congruence

max_threads(self: Congruence) → int

Get the current maximum number of threads.

Returns:

The current maximum number of threads.

Return type:

int

number_of_classes(self: Congruence) → int | PositiveInfinity

Compute the number of classes in the congruence. This function computes the number of classes in the congruence represented by a Congruence instance.

Returns:

The number of congruence classes of a Congruence instance if this number is finite, or POSITIVE_INFINITY in some cases if this number is not finite.

Return type:

int | PositiveInfinity

number_of_generating_pairs(self: Congruence | Kambites | KnuthBendix | ToddCoxeter) → int

Returns the number of generating pairs.

This function returns the number of generating pairs of the congruence.

Returns:

The number of generating pairs.

Return type:

int

Complexity:

Constant.

number_of_runners(self: Congruence) → int

Get the number of runners. This function returns the number of distinct instances of Kambites, KnuthBendix, and/or ToddCoxeter that are contained in a Congruence object.

Returns:

The number of runners.

Return type:

int

presentation(self: Congruence) → Presentation

Get the presentation used to define a Congruence instance (if any). If a Congruence instance is constructed or initialised using a presentation, then this presentation is returned by this function.

Returns:

The presentation used to construct or initialise a Congruence instance.

Return type:

Presentation

reduce(self: Congruence, w: list[int] | str) → list[int] | str

Reduce a word.

This function triggers a full enumeration of an Congruence object and then reduces the word w. As such the returned word is a normal form for the input word.

Parameters:

w (list[int] | str) – the input word.

Returns:

A normal form for the input word.

Return type:

list[int] | str

Raises:

LibsemigroupsError – if any of the values in w is out of range, i.e. they do not belong to presentation().alphabet() and Presentation.throw_if_letter_not_in_alphabet raises.

reduce_no_run(self: Congruence, w: list[int] | str) → list[int] | str

Reduce a word.

If Runner.finished returns True, then this function returns a normal form for the input word w.

Parameters:

w (list[int] | str) – the input word.

Returns:

A word equivalent to the input word.

Return type:

list[int] | str

Raises:

LibsemigroupsError – if any of the values in w is out of range, i.e. they do not belong to presentation().alphabet() and Presentation.throw_if_letter_not_in_alphabet raises.