The Kambites class

Class implementing small overlap class, equality, and normal forms for small overlap monoids.

This page describes the class Kambites for determining the small overlap class of a presentation, and, for small overlap monoids (those with small overlap class 4 or higher) checking equality of words and for computing normal forms. Note that a Kambites instance represents a congruence on the free monoid or semigroup containing the rules of a presentation used to construct the instance, and the Kambites.generating_pairs. As such generating pairs or rules are interchangeable in the context of Kambites objects.

Contents

`Kambites`	Class implementing small overlap class, equality, and normal forms for small overlap monoids.
`Kambites.add_generating_pair`(…)	Add a generating pair.
`Kambites.contains`(…)	Check containment of a pair of words.
`Kambites.copy`(…)	Copy a `Kambites` object.
`Kambites.currently_contains`(…)	Check whether a pair of words is already known to belong to the congruence.
`Kambites.generating_pairs`(…)	Get the generating pairs of the congruence.
`Kambites.init`(…)	Overloaded function.
`Kambites.kind`(…)	The kind of the congruence (1- or 2-sided).
`Kambites.number_of_classes`(…)	Compute the number of classes in the congruence.
`Kambites.number_of_generating_pairs`(…)	Returns the number of generating pairs.
`Kambites.presentation`(…)	Get the presentation used to define a `Kambites` instance (if any).
`Kambites.reduce`(…)	Reduce a word.
`Kambites.reduce_no_run`(…)	Reduce a word.
`Kambites.small_overlap_class`(…)	Get the small overlap class.
`Kambites.ukkonen`(…)	Returns the generalised suffix tree used to compute pieces.

Full API

class Kambites

__init__(*args, **kwargs)

Overloaded function.

__init__(word: type) → None

Default constructor.

This function default constructs an uninitialised Kambites instance.

Keyword Arguments:

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

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

Construct from congruence_kind and Presentation.

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

Kambites instances can only be used to compute two-sided congruences, and so the first parameter knd must always be congruence_kind.twosided. The parameter knd is included for uniformity of interface between with KnuthBendix, ToddCoxeter, and Congruence.

Parameters:

knd (congruence_kind) – the kind (onesided or twosided) of the congruence.
p (Presentation) – the presentation.

Raises:

LibsemigroupsError – if knd is not congruence_kind.twosided.
LibsemigroupsError – if p is not valid.

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

Add a generating pair.

This function adds a generating pair to the congruence represented by a Kambites 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:

Kambites

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.
LibsemigroupsError – if Runner.started returns True.
TypeError – if the type of the arguments is not the same as the type of the words in Kambites.presentation.

contains(self: Kambites, 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 Kambites instance.

Parameters:

u (list[int] | str) – the first word.
v (list[int] | str) – the second word.

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.
LibsemigroupsError – if small_overlap_class is not at least \(4\).

copy(self: Kambites) → Kambites

Copy a Kambites object.

Returns:: A copy.
Return type:: Kambites

currently_contains(self: Kambites, 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 Kambites 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:

u (list[int] | str) – the first word.
v (list[int] | str) – the second word.

Returns:

tril.true if the words are known to belong to the congruence;
tril.false if the words are known to not belong to the congruence;
tril.unknown otherwise.

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.
LibsemigroupsError – if small_overlap_class is known and not at least \(4\).

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

Get the generating pairs of the congruence.

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

Returns:: The list of generating pairs.
Return type:: list[list[int] | str]

init(*args, **kwargs)

Overloaded function.

init(self: Kambites) → Kambites

Re-initialize a Kambites instance.

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

Returns:: self.
Return type:: Kambites

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

Re-initialize a Kambites instance.

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

Parameters:

knd (congruence_kind) – the kind (onesided or twosided) of the congruence.
p (Presentation) – the presentation.

Returns:

self.

Return type:

Kambites

Raises:

LibsemigroupsError – if p is not valid.
LibsemigroupsError – if knd is not congruence_kind.twosided.

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.

number_of_classes(self: Kambites) → int | PositiveInfinity

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

This function computes the number of classes in the congruence represented by a Kambites instance if the small_overlap_class is at least \(4\). Kambites instances can only compute the number of classes if the condition of the previous sentence is fulfilled, and in this case the number of classes is always POSITIVE_INFINITY. Otherwise an exception is raised.

Returns:: The number of congruence classes of a Kambites instance if this number is finite, or POSITIVE_INFINITY in some cases if this number is not finite.
Return type:: int | PositiveInfinity
Raises:: LibsemigroupsError – if knd is not congruence_kind.twosided.

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.

presentation(self: Kambites) → Presentation

Get the presentation used to define a Kambites instance (if any). If a Kambites 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 Kambites instance.
Return type:: Presentation

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

Reduce a word.

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

If the Kambites.small_overlap_class is not at least \(4\), then an exception is thrown.

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.
LibsemigroupsError – if small_overlap_class is not at least \(4\).

reduce_no_run(self: Kambites, 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.

If the Kambites.small_overlap_class is not at least \(4\), then an exception is thrown.

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.

small_overlap_class(self: Kambites) → int | PositiveInfinity

Get the small overlap class.

If \(S\) is a finitely presented semigroup or monoid with generating set \(A\), then a word \(w\) over \(A\) is a piece if \(w\) occurs as a factor in at least two of the relations defining \(S\) or if it occurs as a factor of one relation in two different positions (possibly overlapping). A finitely presented semigroup \(S\) satisfies the condition \(C(n)\), for a positive integer \(n\) if the minimum number of pieces in any factorisation of a word occurring as the left or right hand side of a relation of \(S\) is at least \(n\).

Returns:: The greatest positive integer \(n\) such that the finitely semigroup or monoid represented by self satisfies the condition \(C(n)\) ; or POSITIVE_INFINITY if no word occurring in a relation can be written as a product of pieces.
Return type:: int | PositiveInfinity
Complexity:: The current implementation has complexity no worse than \(O(m ^ 3)\) where \(m\) is the sum of the lengths of the words occurring in the relations of the semigroup.

ukkonen(self: Kambites) → Ukkonen

Returns the generalised suffix tree used to compute pieces.

This function returns the generalised suffix tree Ukkonen object containing the relation words of a Kambites object, that is used to determine the pieces, and decompositions of the relation words.

Returns:: The generalised suffix tree containing the relation words.
Return type:: Ukkonen