Helpers functions for low-index congruences

This page contains the documentation for various helper functions for manipulating Sims1, Sims2, RepOrc or MinimalRepOrc objects. All such functions are contained in the submodule libsemigroups_pybind11.sims.

Contents

`is_maximal_right_congruence`(…)	Check if a word graph defines a maximal right congruence on an f.p.
`is_right_congruence`(…)	Check if a word graph defines a right congruence on an f.p.
`is_right_congruence_of_dual`(…)	Check if a word graph defines a right congruence on the dual of an f.p.
`is_two_sided_congruence`(…)	Check if a word graph defines a two sided congruence on an f.p.
`poset`(…)	Overloaded function.
`right_generating_pairs`(…)	Overloaded function.
`two_sided_generating_pairs`(…)	Overloaded function.

Full API

The full API for the helper functions is given below.

sims.is_maximal_right_congruence(p: Presentation, wg: WordGraph) → bool

Check if a word graph defines a maximal right congruence on an f.p. semigroup or monoid.

Returns True if the word graph wg defines a maximal right congruence on the semigroup or monoid defined by p and False otherwise.

Parameters:

p (Presentation) – A presentation.
wg (WordGraph) – A word graph.

Returns:

An boolean.

Return type:

bool

sims.is_right_congruence(p: Presentation, wg: WordGraph) → bool

Check if a word graph defines a right congruence on an f.p. semigroup or monoid.

Returns True if the word graph wg defines a right congruence on the semigroup or monoid defined by p and False otherwise.

Parameters:

p (Presentation) – A presentation.
wg (WordGraph) – A word graph.

Returns:

An boolean.

Return type:

bool

sims.is_right_congruence_of_dual(p: Presentation, wg: WordGraph) → bool

Check if a word graph defines a right congruence on the dual of an f.p. semigroup or monoid.

Returns True if the word graph wg defines a right congruence on the dual of the semigroup or monoid defined by p and False otherwise. This is equivalent to checking if the word graph defines a left congruence in the semigroup or monoid defined by p.

Parameters:

p (Presentation) – A presentation.
wg (WordGraph) – A word graph.

Returns:

An boolean.

Return type:

bool

sims.is_two_sided_congruence(p: Presentation, wg: WordGraph) → bool

Check if a word graph defines a two sided congruence on an f.p. semigroup or monoid.

Returns True if the word graph wg defines a two-sided congruence on the semigroup or monoid defined by p and False otherwise.

Parameters:

p (Presentation) – A presentation.
wg (WordGraph) – A word graph.

Returns:

An boolean.

Return type:

bool

sims.poset(*args, **kwargs)

Overloaded function.

sims.poset(sims: Sims1, n: int) → Matrix

Compute the inclusion poset of a collection of congruences returned by a Sims1 object with at most n classes.

This function returns a boolean matrix whose \((i, j)\)-th entry is 1 if and only if the congruence defined by the \(i\)-th word graph returned by Sims1.iterator with input n is a subrelation of the congruence defined by the \(j\)-th word graph.

When n is large enough, so that Sims1 computes all right congruences of a given semigroup or monoid, then this is equivalent to computing the right congruence lattice of the semigroup or monoid.

Parameters:

sims (Sims1) – A Sims1 object.
n (int) – Maximum number of congruence classes.

Returns:

A boolean matrix defining the congruence poset.

Return type:

Matrix

sims.poset(sims: Sims2, n: int) → Matrix

Compute the inclusion poset of a collection of congruences returned by a Sims2 object with at most n classes.

This function returns a boolean matrix whose \((i, j)\)-th entry is 1 if and only if the congruence defined by the \(i\)-th word graph returned by Sims2.iterator with input n is a subrelation of the congruence defined by the \(j\)-th word graph.

When n is large enough, so that Sims2 computes all two-sided congruences of a given semigroup or monoid, then this is equivalent to computing the two-sided congruence lattice of the semigroup or monoid.

Parameters:

sims (Sims2) – A Sims2 object.
n (int) – Maximum number of congruence classes.

Returns:

A boolean matrix defining the congruence poset.

Return type:

Matrix

sims.right_generating_pairs(*args, **kwargs)

Overloaded function.

sims.right_generating_pairs(p: Presentation, wg: WordGraph) → collections.abc.Iterator[tuple[list[int], list[int]]]

Compute the right congruence generating pairs of a word graph on an f.p. semigroup or monoid.

This function returns the right congruence generating pairs of the right congruence defined by the word graph wg on the semigroup or monoid defined by p.

Parameters:

p (Presentation) – A presentation.
wg (WordGraph) – A word graph.

Returns:

An iterator of generating pairs.

Return type:

collections.abc.Iterator[tuple[list[int], list[int]]]

Raises:

LibsemigroupsError – if the argument wg does not define a right congruence on the semigroup or monoid defined by p.

sims.right_generating_pairs(wg: WordGraph) → collections.abc.Iterator[tuple[list[int], list[int]]]

Compute the right congruence generating pairs of a word graph on the free monoid.

This function returns the right congruence generating pairs of the right congruence defined by the word graph wg on the free monoid.

Parameters:: wg (WordGraph) – A word graph.
Returns:: An iterator of generating pairs.
Return type:: collections.abc.Iterator[tuple[list[int], list[int]]]
Raises:: LibsemigroupsError – if the argument wg does not define a right congruence on the free monoid.

sims.two_sided_generating_pairs(*args, **kwargs)

Overloaded function.

sims.two_sided_generating_pairs(p: Presentation, wg: WordGraph) → collections.abc.Iterator[tuple[list[int], list[int]]]

Compute the two-sided congruence generating pairs of a word graph on an f.p. semigroup or monoid.

This function returns the two-sided congruence generating pairs of the two-sided congruence defined by the word graph wg on the semigroup or monoid defined by p.

Parameters:

p (Presentation) – A presentation.
wg (WordGraph) – A word graph.

Returns:

An iterator of generating pairs.

Return type:

collections.abc.Iterator[tuple[list[int], list[int]]]

Raises:

LibsemigroupsError – if the argument wg does not define a two-sided congruence on the semigroup or monoid defined by p.

Note

The generating pairs of a two-sided congruence \(\rho\) as a two-sided congruence differ from the generating pairs of \(\rho\) as a right congruence. This function returns the two-sided congruence generating pairs, not the right congruence generating pairs of a two-sided congruence.

sims.two_sided_generating_pairs(wg: WordGraph) → collections.abc.Iterator[tuple[list[int], list[int]]]

Compute the two-sided congruence generating pairs of a word graph on the free monoid.

This function returns the two-sided congruence generating pairs of the two-sided congruence defined by the word graph wg on the free monoid.

Parameters:: wg (WordGraph) – A word graph.
Returns:: An iterator of generating pairs.
Return type:: collections.abc.Iterator[tuple[list[int], list[int]]]
Raises:: LibsemigroupsError – if the argument wg does not define a two-sided congruence on the free monoid.

Note

The generating pairs of a two-sided congruence \(\rho\) as a two-sided congruence differ from the generating pairs of \(\rho\) as a right congruence. This function returns the two-sided congruence generating pairs, not the right congruence generating pairs of a two-sided congruence.