The FroidurePin class

Class implementing the Froidure-Pin algorithm.

A FroidurePin instance represents a semigroup or monoid defined by a collection of generators such as transformations, partial permutations, or matrices.

In the following documentation the type of the elements of the semigroup represented by a FroidurePin instance is denoted by Element.

The class FroidurePin implements the Froidure-Pin algorithm as described in the article [FP97]. A FroidurePin instance is defined by a generating set, and the main function is Runner.run, which implements the Froidure-Pin Algorithm. If Runner.run is invoked and Runner.finished returns True, then the size FroidurePin.size, the left and right Cayley graphs FroidurePin.left_cayley_graph and FroidurePin.right_cayley_graph are determined, and a confluent terminating presentation froidure_pin.rules for the semigroup is known.

See also

Runner.

Important

The class FroidurePin 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 FroidurePin, then you can use thing as if it were an instance of Runner but isinstance(thing, Runner) will return False.

Contents

FroidurePin	Class implementing the Froidure-Pin algorithm.
FroidurePin.add_generator(…)	Add a copy of an element to the generators.
FroidurePin.add_generators(…)	Add a list of generators.
FroidurePin.batch_size(…)	Overloaded function.
FroidurePin.closure(…)	Add non-redundant generators in list.
FroidurePin.contains(…)	Test membership of an element.
FroidurePin.contains_one(…)	Check if the categorical multiplicative identity is an element.
FroidurePin.copy(…)	Copy a FroidurePin object.
FroidurePin.copy_add_generators(…)	Copy and add a list of generators.
FroidurePin.copy_closure(…)	Copy and add non-redundant generators.
FroidurePin.current_elements(…)	Returns an iterator yielding the so-far enumerated elements.
FroidurePin.current_left_cayley_graph(…)	Returns the so-far enumerated left Cayley graph.
FroidurePin.current_length(…)	Returns the length of the short-lex least word equal to the element with given index.
FroidurePin.current_max_word_length(…)	Returns the maximum length of a word in the generators so far computed.
FroidurePin.current_number_of_rules(…)	Returns the number of relations that have been found so far.
FroidurePin.current_position(…)	Find the position of an element with no enumeration.
FroidurePin.current_right_cayley_graph(…)	Returns the so-far enumerated right Cayley graph.
FroidurePin.current_size(…)	Returns the number of elements so far enumerated.
FroidurePin.currently_contains_one(…)	Check if the categorical multiplicative identity is an element.
FroidurePin.degree(…)	Returns the degree of any and all elements.
FroidurePin.enumerate(…)	Enumerate until at least a specified number of elements are found.
FroidurePin.fast_product(…)	Multiply elements via their indices.
FroidurePin.final_letter(…)	Returns the last letter of the element with specified index.
FroidurePin.first_letter(…)	Returns the first letter of the element with specified index.
FroidurePin.generator(…)	Returns the generator with specified index.
FroidurePin.idempotents(…)	Returns an iterator yielding the idempotents.
FroidurePin.init(…)	Overloaded function.
FroidurePin.is_finite(…)	Check finiteness.
FroidurePin.is_idempotent(…)	Check if an element is an idempotent via its index.
FroidurePin.left_cayley_graph(…)	Returns the left Cayley graph.
FroidurePin.length(…)	Returns the length of the short-lex least word equal to the element with given index.
FroidurePin.number_of_elements_of_length(…)	Overloaded function.
FroidurePin.number_of_generators(…)	Returns the number of generators.
FroidurePin.number_of_idempotents(…)	Returns the number of idempotents.
FroidurePin.number_of_rules(…)	Returns the total number of relations in a presentation defining the semigroup.
FroidurePin.position(…)	Find the position of an element with enumeration if necessary.
FroidurePin.position_of_generator(…)	Returns the position in of the generator with specified index.
FroidurePin.prefix(…)	Returns the position of the longest proper prefix.
FroidurePin.reserve(…)	Requests the given capacity for elements.
FroidurePin.right_cayley_graph(…)	Returns the fully enumerated right Cayley graph.
FroidurePin.size(…)	Returns the size of the semigroup represented by a FroidurePin instance.
FroidurePin.sorted_at(…)	Access element specified by sorted index with bound checks.
FroidurePin.sorted_elements(…)	Returns an iterator yielding the sorted elements of a FroidurePin instance.
FroidurePin.sorted_position(…)	Returns the sorted index of an element.
FroidurePin.suffix(…)	Returns the position of the longest proper suffix.
FroidurePin.to_sorted_position(…)	Returns the sorted index of an element via its index.

Full API

class FroidurePin

__init__(self: FroidurePin, gens: list[Element]) → None

Construct from a list of generators.

This function constructs a FroidurePin instance with generators in the list gens.

Parameters:

gens (list[Element]) – the list of generators.

Raises:

LibsemigroupsError – if the generators do not all have the same degree.

add_generator(self: FroidurePin, x: Element) → FroidurePin

Add a copy of an element to the generators.

This function can be used to add new generators to an existing FroidurePin instance in such a way that any previously enumerated data is preserved and not recomputed, or copied. This can be faster than recomputing the semigroup generated by the old generators and the new generators.This function changes the semigroup in-place, thereby invalidating possibly previously known data about the semigroup, such as the left or right Cayley graphs, number of idempotents, and so on.

The generator in x is added regardless of whether or not it is already an element of the semigroup. After calling this function the generator x will be the generator with the largest index. There can be duplicate generators and although they do not count as distinct elements, they do count as distinct generators.

The FroidurePin instance is returned in a state where all of the previously enumerated elements which had been multiplied by all of the old generators, have now been multiplied by all of the old and new generators. This means that after this function is called the semigroup might contain many more elements than before (whether it is fully enumerating or not).

Parameters:

x (Element) – the generator to add.

Returns:

self.

Return type:

FroidurePin

Raises:

• LibsemigroupsError – if the degree of x is incompatible with the existing degree (if any).

• TypeError – if x is not of the same type as the existing generators (if any).

add_generators(self: FroidurePin, gens: list[Element]) → FroidurePin

Add a list of generators.

See add_generator for a detailed description.

Parameters:

gens (list[Element]) – the list of generators.

Returns:

self.

Return type:

FroidurePin

Raises:

• TypeError – if gens is not a list.

• TypeError – if any item in gens is not of the same type as the existing generators (if any).

• LibsemigroupsError – if the degree of any item in gens is incompatible with the existing degree (if any).

batch_size(*args, **kwargs)

Overloaded function.

batch_size(self: FroidurePin) → int

Returns the current value of the batch size.

This function returns the minimum number of elements enumerated in any call to Runner.run.

Returns:

The current value of the batch size.

Return type:

int

Complexity:

Constant.

batch_size(self: FroidurePin, val: int) → FroidurePin

Set a new value for the batch size.

The batch size is the number of new elements to be found by any call to Runner.run. This is used by, for example, FroidurePin.position so that it is possible to find the position of an element after only partially enumerating the semigroup.The default value of the batch size is 8192.

Parameters:

val (int) – the new value for the batch size.

Returns:

self.

Return type:

FroidurePin

Complexity:

Constant.

closure(self: FroidurePin, gens: list[Element]) → FroidurePin

Add non-redundant generators in list.

This function differs from FroidurePin.add_generators in that it tries to add the new generators one by one, and only adds those generators that are not products of existing generators (including any new generators that were added before). The generators are added in the order they occur in gens.

This function changes a FroidurePin instance in-place, thereby invalidating some previously computed information, such as the left or right Cayley graphs, or number of idempotents, for example.

Parameters:

gens (list[Element]) – the list of generators.

Returns:

self.

Return type:

FroidurePin

Raises:

• LibsemigroupsError – if any of the elements in gens do not have degree compatible with any existing elements of the FroidurePin instance.

• LibsemigroupsError – if the elements in gens do not all have the same degree.

contains(self: FroidurePin, x: Element) → bool

Test membership of an element.

This function returns True if x belongs to a FroidurePin instance and False if it does not.

Parameters:

x (Element) – a possible element.

Returns:

Whether or not the element x is contained in a FroidurePin instance.

Return type:

bool

contains_one(self: FroidurePin) → bool

Check if the categorical multiplicative identity is an element.

Returns:

Whether or not the one of any of the elements belongs to the semigroup.

Return type:

bool

Complexity:

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by self, and \(n\) is the return value of FroidurePin.number_of_generators.

copy(self: FroidurePin) → FroidurePin

Copy a FroidurePin object.

Returns:

A copy.

Return type:

FroidurePin

copy_add_generators(self: FroidurePin, gens: list[Element]) → FroidurePin

Copy and add a list of generators.

This function is equivalent to copying a FroidurePin instance and then calling FroidurePin.add_generators on the copy. But this function avoids copying the parts of the initial instance that are immediately invalidated by FroidurePin.add_generators.

Parameters:

gens (list[Element]) – the list of generators.

Returns:

A new FroidurePin instance by value generated by the generators of self and gens.

Return type:

FroidurePin

Raises:

• LibsemigroupsError – if any of the elements in gens do not have degree compatible with any existing elements of the FroidurePin instance.

• LibsemigroupsError – if the elements in gens do not all have the same degree.

copy_closure(self: FroidurePin, gens: list[Element]) → FroidurePin

Copy and add non-redundant generators.

This function is equivalent to copying a FroidurePin instance and then calling closure on the copy. But this function avoids copying the parts of the initial FroidurePin instance that are immediately discarded by closure.

Parameters:

gens (list[Element]) – the list of generators.

Returns:

A new FroidurePin instance by value generated by the generators of self and the non-redundant generators in gens.

Return type:

FroidurePin

Raises:

• LibsemigroupsError – if any of the elements in gens do not have degree compatible with any existing elements of the FroidurePin instance.

• LibsemigroupsError – if the elements in gens do not all have the same degree.

current_elements(self: FroidurePin) → collections.abc.Iterator[Element]

Returns an iterator yielding the so-far enumerated elements.

This function returns an iterator yielding the so-far enumerated elements. Calling this function does not trigger any enumeration.

Parameters:

self (FroidurePin) – the FroidurePin instance.

Returns:

An iterator yielding the so-far enumerated elements.

Return type:

collections.abc.Iterator[Element]

current_left_cayley_graph(self: FroidurePin) → WordGraph

Returns the so-far enumerated left Cayley graph.

This function return the left Cayley graph of the semigroup as it has been enumerated so-far. No enumeration is triggered by calls to this function.

Returns:

The (possibly partially enumerated) left Cayley graph.

Return type:

WordGraph

Complexity:

Constant.

current_length(self: FroidurePin, pos: int) → int

Returns the length of the short-lex least word equal to the element with given index.

This function returns the length of the short-lex least word (in the generators) equal to the element with index pos.

Parameters:

pos (int) – the position.

Returns:

The length of the word equal to the element with index pos.

Return type:

int

Raises:

LibsemigroupsError – if pos is greater than or equal to current_size.

Complexity:

Constant.

See also

length.

current_max_word_length(self: FroidurePin) → int

Returns the maximum length of a word in the generators so far computed. Every element of the semigroup can be expressed as the short-lex least product of the generators that equals that element. This function returns the length of the longest short-lex least word in the generators that has so far been enumerated.

Returns:

The maximum length of a word so-far enumerated.

Return type:

int

Complexity:

Constant.

current_number_of_rules(self: FroidurePin) → int

Returns the number of relations that have been found so far. This is only guaranteed to be the actual number of relations in a presentation defining the semigroup if the semigroup is fully enumerated.

Returns:

The number of rules so-far enumerated.

Return type:

int

Complexity:

Constant.

current_position(self: FroidurePin, x: Element) → int | Undefined

Find the position of an element with no enumeration.

This function returns the position of the element x in the semigroup if it is already known to belong to the semigroup or UNDEFINED. This function finds the position of the element x if it is already known to belong to a FroidurePin instance, and UNDEFINED if not. If a FroidurePin instance is not yet fully enumerated, then this function may return UNDEFINED when x does belong to the fully enumerated instance.

Parameters:

x (Element) – a possible element.

Returns:

The position of x if it belongs to a FroidurePin instance and UNDEFINED if not.

Return type:

int | Undefined

See also

position and sorted_position.

current_right_cayley_graph(self: FroidurePin) → WordGraph

Returns the so-far enumerated right Cayley graph.

This function return the right Cayley graph of the semigroup as it has been enumerated so-far. No enumeration is triggered by calls to this function.

Returns:

The (possibly partially enumerated) left Cayley graph.

Return type:

WordGraph

Complexity:

Constant.

current_size(self: FroidurePin) → int

Returns the number of elements so far enumerated. This is only the actual size of the semigroup if the semigroup is fully enumerated.

Returns:

The current number of elements that have been enumerated.

Return type:

int

Complexity:

Constant.

currently_contains_one(self: FroidurePin) → bool

Check if the categorical multiplicative identity is an element.

Returns:

Whether or not the one of any of the elements belongs to the semigroup.

Return type:

bool

Complexity:

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by self, and \(n\) is the return value of FroidurePin.number_of_generators.

degree(self: FroidurePin) → int

Returns the degree of any and all elements.

Returns:

The degree of the elements contained in the semigroup.

Return type:

int

Complexity:

Constant.

enumerate(self: FroidurePin, limit: int) → None

Enumerate until at least a specified number of elements are found.

If the semigroup is already fully enumerated, or the number of elements previously enumerated exceeds limit, then calling this function does nothing. Otherwise, Runner.run attempts to find at least the maximum of limit and batch_size elements of the semigroup.

Parameters:

limit (int) – the limit.

Complexity:

At worst \(O(mn)\) where \(m\) equals limit and \(n\) is the return value of FroidurePin.number_of_generators.

fast_product(self: FroidurePin, i: int, j: int) → int

Multiply elements via their indices.

This function returns the position of the product of the element with index i and the element with index j.

This function either:

• follows the path in the right or left Cayley graph from i to j, whichever is shorter using froidure_pin.product_by_reduction; or

• multiplies the elements in positions i and j together;

whichever is better.

For example, if the complexity of the multiplication is linear and self is a semigroup of transformations of degree 20, and the shortest paths in the left and right Cayley graphs from i to j are of length 100 and 1131, then it is better to just multiply the transformations together.

Parameters:

• i (int) – the index of the first element to multiply.

• j (int) – the index of the second element to multiply.

Returns:

The index of the product.

Return type:

int

Raises:

LibsemigroupsError – if the values i and j are greater than or equal to FroidurePin.current_size.

final_letter(self: FroidurePin, pos: int) → int

Returns the last letter of the element with specified index.

This function returns the final letter of the element in position pos of the semigroup, which is the index of the generator corresponding to the final letter of the element.

Parameters:

pos (int) – the position.

Returns:

The last letter in the minimal factorisation of the element with given position.

Return type:

int

Raises:

LibsemigroupsError – if pos is greater than or equal to current_size.

Complexity:

Constant.

first_letter(self: FroidurePin, pos: int) → int

Returns the first letter of the element with specified index.

This function returns the first letter of the element in position pos of the semigroup, which is the index of the generator corresponding to the first letter of the element.

Parameters:

pos (int) – the position.

Returns:

The first letter in the minimal factorisation of the element with given position.

Return type:

int

Raises:

LibsemigroupsError – if pos is greater than or equal to current_size.

Complexity:

Constant.

generator(self: FroidurePin, i: int) → Element

Returns the generator with specified index.

This function returns the generator with index i, where the order is that in which the generators were added at construction, or via init, add_generator, add_generators, closure, copy_closure, or copy_add_generators.

Parameters:

i (int) – the index of a generator.

Returns:

The generator with given index.

Return type:

Element

Raises:

LibsemigroupsError – if i is greater than or equal to number_of_generators().

idempotents(self: FroidurePin) → collections.abc.Iterator[Element]

Returns an iterator yielding the idempotents.

If next is called on the returned iterator, then it yields the first idempotent in the semigroup, and every subsequent call to next yields the next idempotent.

Returns:

An iterator yielding the idempotents.

Return type:

collections.abc.Iterator[Element]

init(*args, **kwargs)

Overloaded function.

init(self: FroidurePin) → FroidurePin

Reinitialize a FroidurePin object.

This function re-initializes a FroidurePin object so that it is in the same state as if it had just been default constructed.

Returns:

self.

Return type:

FroidurePin

init(self: FroidurePin, gens: list[Element]) → FroidurePin

Reinitialize a FroidurePin object from a list of generators.

This function re-initializes a FroidurePin object so that it is in the same state as if it had just been constructed from gens.

Parameters:

gens (list[Element]) – the generators.

Returns:

self.

Return type:

FroidurePin

Raises:

LibsemigroupsError – if the elements in gens do not all have the same degree.

is_finite(self: FroidurePin) → tril

Check finiteness.

This function returns tril.true if the semigroup represented by self is finite, tril.false if it is infinite, and tril.unknown if it is not known. For some types of elements, such as matrices over the integers, for example, it is undecidable, in general, if the semigroup generated by these elements is finite or infinite. On the other hand, for other types, such as transformation, the semigroup is always finite.

Returns:

If the FroidurePin object is finite, or not finite, or it isn’t possible to answer this question without performing a full enumeration.

Return type:

tril

is_idempotent(self: FroidurePin, i: int) → bool

Check if an element is an idempotent via its index.

This function returns True if the element in position i is an idempotent and False if it is not.

Parameters:

i (int) – the index of the element.

Returns:

A value of type bool.

Return type:

bool

Raises:

LibsemigroupsError – if i is greater than or equal to the size of the FroidurePin instance.

left_cayley_graph(self: FroidurePin) → WordGraph

Returns the left Cayley graph.

This function triggers a full enumeration, and then returns the left Cayley graph of the semigroup represented by a FroidurePin instance.

Returns:

The fully enumerated left Cayley graph.

Return type:

WordGraph

Complexity:

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by self, and \(n\) is the return value of FroidurePin.number_of_generators.

length(self: FroidurePin, pos: int) → int

Returns the length of the short-lex least word equal to the element with given index.

Parameters:

pos (int) – the position.

Returns:

The length of the element with index pos.

Return type:

int

Raises:

LibsemigroupsError – if pos is greater than or equal to size.

Complexity:

Constant.

See also

current_length.

number_of_elements_of_length(*args, **kwargs)

Overloaded function.

number_of_elements_of_length(self: FroidurePin, len: int) → int

Returns the number of elements so far enumerated with given length.

This function returns the number of elements that have been enumerated so far with length len. This function does not trigger any enumeration.

Parameters:

len (int) – the length.

Returns:

The number of elements with length len.

Return type:

int

Complexity:

Constant.

number_of_elements_of_length(self: FroidurePin, min: int, max: int) → int

Returns the number of elements so far enumerated with length in a given range.

This function returns the number of elements that have been enumerated so far with length in the range \([min, max)\). This function does not trigger any enumeration.

Parameters:

• min (int) – the minimum length.

• max (int) – the maximum length plus one.

Returns:

The number of elements with lengths in the specified range.

Return type:

int

Complexity:

Constant.

number_of_generators(self: FroidurePin) → int

Returns the number of generators.

This function returns the number of generators of a FroidurePin instance.

Returns:

The number of generators.

Return type:

int

number_of_idempotents(self: FroidurePin) → int

Returns the number of idempotents.

This function returns the number of idempotents in the semigroup represented by a FroidurePin instance. Calling this function triggers a full enumeration.

Returns:

The number of idempotents.

Return type:

int

number_of_rules(self: FroidurePin) → int

Returns the total number of relations in a presentation defining the semigroup. This function triggers a full enumeration of the semigroup.

Returns:

The number of rules so-far found.

Return type:

int

Complexity:

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by self, and \(n\) is the return value of FroidurePin.number_of_generators.

position(self: FroidurePin, x: Element) → int | Undefined

Find the position of an element with enumeration if necessary.

This function the position of x in a FroidurePin instance, or UNDEFINED if x is not an element.

Parameters:

x (Element) – a possible element.

Returns:

The position of x.

Return type:

int | Undefined

See also

current_position and sorted_position.

position_of_generator(self: FroidurePin, i: int) → int

Returns the position in of the generator with specified index.

In many cases FroidurePin.current_position called with argument i will return i, examples of when this will not be the case are:

• there are duplicate generators;

• FroidurePin.add_generators was called after the semigroup was already partially enumerated.

Parameters:

i (int) – the index of the generator.

Returns:

The position of the generator with index i.

Return type:

int

Raises:

LibsemigroupsError – if i is greater than or equal to FroidurePin.number_of_generators.

Complexity:

Constant.

prefix(self: FroidurePin, pos: int) → int

Returns the position of the longest proper prefix.

Returns the position of the prefix of the element x in position pos (of the semigroup) of length one less than the length of x.

Parameters:

pos (int) – the position.

Returns:

The position of the prefix.

Return type:

int

Raises:

LibsemigroupsError – if pos is greater than or equal to current_size.

Complexity:

Constant.

reserve(self: FroidurePin, val: int) → FroidurePin

Requests the given capacity for elements.

The parameter val is also used to initialise certain data members of a FroidurePin instance. If you know a good upper bound for the size of your semigroup, then it might be a good idea to call this function with that upper bound as an argument; this can significantly improve the performance of the Runner.run function, and consequently every other function too.

Parameters:

val (int) – the number of elements to reserve space for.

Returns:

self.

Return type:

FroidurePin

right_cayley_graph(self: FroidurePin) → WordGraph

Returns the fully enumerated right Cayley graph.

Returns:

The fully enumerated right Cayley graph.

Return type:

WordGraph

Complexity:

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by self, and \(n\) is the return value of FroidurePin.number_of_generators.

size(self: FroidurePin) → int

Returns the size of the semigroup represented by a FroidurePin instance.

Returns:

The size of the semigroup.

Return type:

int

Complexity:

At worst \(O(|S|n)\) where \(S\) is the semigroup represented by self, and \(n\) is the return value of FroidurePin.number_of_generators.

sorted_at(self: FroidurePin, i: int) → Element

Access element specified by sorted index with bound checks.

This function triggers a full enumeration, and the parameter i is the index when the elements are sorted.

Parameters:

i (int) – the sorted index of the element to access.

Returns:

The element with index i (if any).

Return type:

Element

Raises:

LibsemigroupsError – if i is greater than or equal to the return value of FroidurePin.size.

sorted_elements(self: FroidurePin) → collections.abc.Iterator[Element]

Returns an iterator yielding the sorted elements of a FroidurePin instance.

Returns:

An iterator yielding the sorted elements.

Return type:

collections.abc.Iterator[Element]

sorted_position(self: FroidurePin, x: Element) → int | Undefined

Returns the sorted index of an element.

This function returns the position of x in the elements of a FroidurePin when they are sorted, or UNDEFINED if x is not an element.

Parameters:

x (Element) – a possible element.

Returns:

The position of x in the sorted list of elements.

Return type:

int | Undefined

See also

current_position and position.

suffix(self: FroidurePin, pos: int) → int

Returns the position of the longest proper suffix.

Returns the position of the suffix of the element x in position pos (of the semigroup) of length one less than the length of x.

Parameters:

pos (int) – the position.

Returns:

The position of the suffix of the element

Return type:

int

Raises:

LibsemigroupsError – if pos is greater than or equal to current_size.

Complexity:

Constant.

to_sorted_position(self: FroidurePin, i: int) → int | Undefined

Returns the sorted index of an element via its index.

This function returns the position of the element with index i when the elements are sorted, or UNDEFINED if i is greater than FroidurePin.size.

Parameters:

i (int) – the index of the element.

Returns:

The sorted position of the element with position i.

Return type:

int | Undefined