FroidurePin helpers

This page contains the documentation for various helper functions for manipulating FroidurePin objects.

Contents

`current_minimal_factorisation`(…)	Returns the short-lex least word representing an element given by index.
`current_normal_forms`(…)	Returns an iterator yielding the so-far enumerated normal forms (if any).
`current_position`(…)	Returns the position corresponding to a word.
`current_rules`(…)	Returns an iterator yielding the so-far enumerated rules.
`equal_to`(…)	Check equality of words in the generators.
`factorisation`(…)	Returns a word containing a factorisation (in the generators) of an element.
`minimal_factorisation`(…)	Returns a word containing a minimal factorisation (in the generators) of an element.
`normal_forms`(…)	Returns an iterator yielding normal forms.
`position`(…)	Returns the position corresponding to a word.
`product_by_reduction`(…)	Compute a product using the Cayley graph.
`rules`(…)	Returns an iterator yielding the rules.
`to_element`(…)	Convert a word in the generators to an element.

Full API

This page contains the documentation for various helper functions for manipulating FroidurePin objects. All such functions are contained in the submodule libsemigroups_pybind11.froidure_pin.

froidure_pin.current_minimal_factorisation(fp: FroidurePin, pos: int) → list[int]

Returns the short-lex least word representing an element given by index.

This function returns the short-lex least word (in the generators) representing the element in fp with index pos.

Parameters:

fp (FroidurePin) – the FroidurePin object.
pos (int) – the index of the element whose factorisation is sought.

Returns:

A minimal factorisation of the element with index pos.

Return type:

list[int]

Raises:

LibsemigroupsError – if pos is not strictly less than FroidurePin.current_size.

Complexity:

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

Note

No enumeration is triggered by calling this function.

froidure_pin.current_normal_forms(fp: FroidurePin) → collections.abc.Iterator[list[int]]

Returns an iterator yielding the so-far enumerated normal forms (if any).

This function returns an iterator yielding the normal forms of the semigroup represented by fp instance (if any). This function does not perform any enumeration of fp. If you want to obtain the complete set of rules, then use normal_forms instead.

Parameters:: fp (FroidurePin) – the FroidurePin object.
Returns:: An iterator yielding a list[int].
Return type:: collections.abc.Iterator[list[int]]
Complexity:: Constant.

froidure_pin.current_position(fp: FroidurePin, w: list[int]) → int | Undefined

Returns the position corresponding to a word.

This function returns the position in fp corresponding to the the word w (in the generators). No enumeration is performed, and UNDEFINED is returned if the position of the element corresponding to w cannot be determined.

Parameters:

fp (FroidurePin) – the FroidurePin instance.
w (list[int]) – a word in the generators.

Returns:

The current position of the element represented by a word.

Return type:

int | Undefined

Raises:

LibsemigroupsError – if w contains a value that is not strictly less than FroidurePin.number_of_generators.

Complexity:

\(O(n)\) where \(n\) is the length of the word w.

froidure_pin.current_rules(fp: FroidurePin) → collections.abc.Iterator[tuple[list[int], list[int]]]

Returns an iterator yielding the so-far enumerated rules.

This function returns an iterator yielding the rules in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by fp. This function does not perform any enumeration of fp. If you want to obtain the complete set of rules, then use rules instead.

Parameters:: fp (FroidurePin) – the FroidurePin object.
Returns:: An iterator.
Return type:: collections.abc.Iterator[tuple[list[int], list[int]]]
Complexity:: Constant

>>> S = FroidurePin(
... BMat8([[1,  0,  0,  0],
...        [1,  0,  0,  0],
...        [1,  0,  0,  0],
...        [1,  0,  0,  0]]),
... BMat8([[0,  1,  0,  0],
...        [0,  1,  0,  0],
...        [0,  1,  0,  0],
...        [0,  1,  0,  0]]),
... BMat8([[0,  0,  1,  0],
...        [0,  0,  1,  0],
...        [0,  0,  1,  0],
...        [0,  0,  1,  0]]),
... BMat8([[0,  0,  0,  1],
...        [0,  0,  0,  1],
...        [0,  0,  0,  1],
...        [0,  0,  0,  1]]))
>>> S.size()
4
>>> list(S.rules())
[([0, 0], [0]),
 ([0, 1], [1]),
 ([0, 2], [2]),
 ([0, 3], [3]),
 ([1, 0], [0]),
 ([1, 1], [1]),
 ([1, 2], [2]),
 ([1, 3], [3]),
 ([2, 0], [0]),
 ([2, 1], [1]),
 ([2, 2], [2]),
 ([2, 3], [3]),
 ([3, 0], [0]),
 ([3, 1], [1]),
 ([3, 2], [2]),
 ([3, 3], [3])]

froidure_pin.equal_to(fp: FroidurePin, x: list[int], y: list[int]) → bool

Check equality of words in the generators.

This function returns True if the parameters x and y represent the same element of fp and False otherwise.

Parameters:

fp (FroidurePin) – the FroidurePin instance.
x (list[int]) – the first word for comparison.
y (list[int]) – the second word for comparison.

Returns:

Whether or not the words x and y represent the same element.

Return type:

bool

Raises:

LibsemigroupsError – if x or y contains any value that is not strictly less than FroidurePin.number_of_generators.

Note

No enumeration of fp is triggered by calls to this function.

froidure_pin.factorisation(fp: FroidurePin, x: Element | int) → list[int]

Returns a word containing a factorisation (in the generators) of an element.

This function returns a word in the generators that equals the given element x. The key difference between this function and minimal_factorisation, is that the resulting factorisation may not be minimal.

Parameters:

fp (FroidurePin) – the FroidurePin instance.
x (Element | int) – a possible element, or index of element, to factorise.

Returns:

Returns a word in the generators which evaluates to x.

Return type:

list[int]

Raises:

LibsemigroupsError – if x is an Element and x does not belong to fp.
LibsemigroupsError – if x is an int and x is greater than or equal to FroidurePin.size.

froidure_pin.minimal_factorisation(fp: FroidurePin, x: Element | int) → list[int]

Returns a word containing a minimal factorisation (in the generators) of an element.

This function returns the short-lex minimum word (if any) in the generators that evaluates to x.

Parameters:

fp (FroidurePin) – the FroidurePin instance.
x (Element | int) – a possible element, or index of element, to factorise.

Returns:

A word in the generators that evaluates to x.

Return type:

list[int]

Raises:

LibsemigroupsError – if x is an Element and x does not belong to fp.
LibsemigroupsError – if x is an int and x is greater than or equal to FroidurePin.size.

froidure_pin.normal_forms(fp: FroidurePin) → collections.abc.Iterator[list[int]]

Returns an iterator yielding normal forms. This function returns an iterator yielding normal forms for the elements of the semigroup represented by fp instance. This function performs a full enumeration of fp. If you want to obtain the current normal forms without triggering an enumeration, then use current_normal_forms instead.

Parameters:: fp (FroidurePin) – the FroidurePin object.
Returns:: An iterator of normal forms.
Return type:: collections.abc.Iterator[list[int]]

froidure_pin.position(fp: FroidurePin, w: list[int]) → int

Returns the position corresponding to a word.

This function returns the position in fp corresponding to the word w. A full enumeration is triggered by calls to this function.

Parameters:

fp (FroidurePin) – the FroidurePin instance.
w (list[int]) – a word in the generators.

Returns:

The position of the element represented by a word.

Return type:

int

Raises:

LibsemigroupsError – if w contains any values that are not strictly less than FroidurePin.number_of_generators.

Complexity:

\(O(n)\) where \(n\) is the length of the word w.

froidure_pin.product_by_reduction(fp: FroidurePin, i: int, j: int) → int

Compute a product using the Cayley graph.

This function finds the product of fp[i] and fp[j] by following the path in the right Cayley graph from i labelled by the word froidure_pin.minimal_factorisation(fp, j) or, if froidure_pin.minimal_factorisation(fp, i) is shorter, by following the path in the left Cayley graph from j labelled by froidure_pin.minimal_factorisation(fp, i).

Parameters:

fp (FroidurePin) – the FroidurePin object.
i (int) – the index of an element.
j (int) – another index of an element.

Returns:

The index of the product.

Return type:

int

Raises:

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

Complexity:

\(O(n)\) where \(n\) is the minimum of the lengths of minimal_factorisation(fp, i) and minimal_factorisation(fp, j).

froidure_pin.rules(fp: FroidurePin) → collections.abc.Iterator[tuple[list[int], list[int]]]

Returns an iterator yielding the rules.

This function returns an iterator yielding the rules in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by fp. This function performs a full enumeration of fp If you want to obtain the current set of rules without triggering any enumeration, then use current_rules instead.

Parameters:: fp (FroidurePin) – the FroidurePin object.
Returns:: An iterator yielding rules.
Return type:: collections.abc.Iterator[tuple[list[int], list[int]]]

froidure_pin.to_element(fp: FroidurePin, w: list[int]) → Element

Convert a word in the generators to an element.

This function returns the element of fp obtained by evaluating w.

Parameters:

fp (FroidurePin) – the FroidurePin instance.
w (list[int]) – the word in the generators to evaluate.

Returns:

The element of fp corresponding to the word w.

Return type:

Element

Raises:

LibsemigroupsError – if w is not a valid word in the generators, i.e. if it contains a value greater than or equal to the number of generators.

Note

No enumeration of fp is triggered by calls to this function.