Factorisation, products, and relations

This page contains information about the member functions of the FroidurePinBase class related to factorising elements, products, and defining relations.

inline const_rule_iterator libsemigroups::FroidurePinBase::cbegin_rules() const

Returns a forward iterator pointing to the first rule (if any).

Returns a forward iterator pointing to the first rule in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by this.

This function does not perform any enumeration of the FroidurePin. If you want to obtain the complete set of rules, then it is necessary to call run() first.

See also

cend_rules

Parameters

(None).

Complexity

Constant

Iterator validity

The iterators returned by this function are valid until the underlying FroidurePin instance is deleted.

Example

FroidurePin<BMat8> S;
S.add_generator(BMat8({{1, 0, 0, 0},
                       {1, 0, 0, 0},
                       {1, 0, 0, 0},
                       {1, 0, 0, 0}}));
S.add_generator(BMat8({{0, 1, 0, 0},
                       {0, 1, 0, 0},
                       {0, 1, 0, 0},
                       {0, 1, 0, 0}}));
S.add_generator(BMat8({{0, 0, 1, 0},
                       {0, 0, 1, 0},
                       {0, 0, 1, 0},
                       {0, 0, 1, 0}}));
S.add_generator(BMat8({{0, 0, 0, 1},
                       {0, 0, 0, 1},
                       {0, 0, 0, 1},
                       {0, 0, 0, 1}}));
S.size(); // 4
std::vector<relation_type>(S.cbegin_rules(), S.cend_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}}}

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

An iterator of type FroidurePinBase::const_rule_iterator pointing to a relation_type.

inline const_rule_iterator libsemigroups::FroidurePinBase::cend_rules() const

Returns a forward iterator pointing one past the last rule (if any).

Returns a forward iterator pointing one-past-the-last rule (currently known) in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by this.

This function does not perform any enumeration of the FroidurePin. If you want to obtain the complete set of rules, then it is necessary to call run() first.

See also

cbegin_rules

Parameters

(None).

Complexity

Constant

Iterator validity

The iterators returned by this function are valid until the underlying FroidurePin instance is deleted.

Example

FroidurePin<BMat8> S;
S.add_generator(BMat8({{1, 0, 0, 0},
                       {1, 0, 0, 0},
                       {1, 0, 0, 0},
                       {1, 0, 0, 0}}));
S.add_generator(BMat8({{0, 1, 0, 0},
                       {0, 1, 0, 0},
                       {0, 1, 0, 0},
                       {0, 1, 0, 0}}));
S.add_generator(BMat8({{0, 0, 1, 0},
                       {0, 0, 1, 0},
                       {0, 0, 1, 0},
                       {0, 0, 1, 0}}));
S.add_generator(BMat8({{0, 0, 0, 1},
                       {0, 0, 0, 1},
                       {0, 0, 0, 1},
                       {0, 0, 0, 1}}));
S.size(); // 4
std::vector<relation_type>(S.cbegin_rules(), S.cend_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}}}

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

An iterator of type FroidurePinBase::const_rule_iterator pointing to a relation_type.

inline size_t libsemigroups::FroidurePinBase::current_length(element_index_type pos) const

Returns the length of the short-lex least word.

See also

length.

Complexity

Constant.

Parameters

pos – the position

Throws

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

Returns

A value of type letter_type.

inline size_t libsemigroups::FroidurePinBase::current_max_word_length() const noexcept

Returns the maximum length of a word in the generators so far computed.

Every elements 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.

Parameters

(None)

Complexity

Constant.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type size_t.

inline element_index_type libsemigroups::FroidurePinBase::current_position(letter_type i) const

Returns the position in of the generator with specified index.

In many cases current_position(i) will equal i, examples of when this will not be the case are:

Complexity

Constant.

Parameters

i – the index of the generators

Throws

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

Returns

A value of type element_index_type.

inline element_index_type libsemigroups::FroidurePinBase::current_position(std::initializer_list<size_t> const &w) const

Returns the position corresponding to a word.

Returns the position in the semigroup corresponding to the element represented by the word w.

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

This is equivalent to finding the product x of the generators FroidurePin::generator(w[i]) and then calling FroidurePin::current_position with argument x.

See also

FroidurePin::word_to_element.

Complexity

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

Parameters

w – a word in the generators

Throws

LibsemigroupsException – if w contains an value exceeding FroidurePin::number_of_generators.

Returns

A value of type element_index_type or UNDEFINED.

element_index_type libsemigroups::FroidurePinBase::current_position(word_type const &w) const

Returns the position corresponding to a word.

Returns the position in the semigroup corresponding to the element represented by the word w.

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

This is equivalent to finding the product x of the generators FroidurePin::generator(w[i]) and then calling FroidurePin::current_position with argument x.

See also

FroidurePin::word_to_element.

Complexity

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

Parameters

w – a word in the generators

Throws

LibsemigroupsException – if w contains an value exceeding FroidurePin::number_of_generators.

Returns

A value of type element_index_type or UNDEFINED.

inline word_type libsemigroups::FroidurePinBase::factorisation(element_index_type pos)

Returns a word representing an element given by index.

This is the same as the two-argument member function for factorisation, but it returns a word_type by value instead of modifying an argument in-place.

The key difference between this function and minimal_factorisation(element_index_type) is that the resulting factorisation may not be minimal.

Complexity

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

Parameters

pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to size().

Returns

A value of type word_type.

inline void libsemigroups::FroidurePinBase::factorisation(word_type &word, element_index_type pos)

Obtain a word representing an element given by index.

Changes word in-place to contain a word in the generators equal to the pos element of the semigroup.

If pos is less than the size of this semigroup, then this member function changes its first parameter word in-place by first clearing it and then to contain a factorization of the element in position pos of the semigroup with respect to the generators of the semigroup. This function enumerates the semigroup until at least the pos element is known.

The key difference between this function and minimal_factorisation(element_index_type) is that the resulting factorisation may not be minimal.

Complexity

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

Parameters

  • word – the word to clear and change in-place

  • pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to size().

Returns

(None)

inline size_t libsemigroups::FroidurePinBase::length(element_index_type pos)

Returns the length of the short-lex least word.

See also

current_length.

Complexity

Constant.

Parameters

pos – the position

Throws

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

Returns

A value of type letter_type.

inline word_type libsemigroups::FroidurePinBase::minimal_factorisation(element_index_type pos)

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

This is the same as the two-argument member function for minimal_factorisation, but it returns a word_type by value instead of modifying an argument in-place.

Complexity

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

Parameters

pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to size().

Returns

A value of type word_type.

inline void libsemigroups::FroidurePinBase::minimal_factorisation(word_type &word, element_index_type pos)

Obtain a short-lex least word representing an element given by index.

Changes word in-place to contain a minimal word with respect to the short-lex ordering in the generators equal to the pos element of the semigroup.

If pos is less than the size of this semigroup, then this member function changes its first parameter word in-place by first clearing it and then to contain a minimal factorization of the element in position pos of the semigroup with respect to the generators of the semigroup. This function enumerates the semigroup until at least the pos element is known.

Complexity

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

Parameters

  • word – the word to clear and change in-place

  • pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to size().

Returns

(None)

inline void libsemigroups::FroidurePinBase::minimal_factorisation(word_type &word, element_index_type pos) const

Obtain a short-lex least word representing an element given by index.

Changes word in-place to contain a minimal word with respect to the short-lex ordering in the generators equal to the pos element of the semigroup. No further enumeration is performed.

Complexity

Constant.

Parameters

  • word – the word to clear and change in-place

  • pos – the index of the element whose factorisation is sought

Throws

LibsemigroupsException – if pos is greater than or equal to current_size().

Returns

(None)

inline size_t libsemigroups::FroidurePinBase::number_of_rules()

Returns the total number of relations in the presentation.

See also

cbegin_rules and cend_rules.

Complexity

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

Parameters

(None)

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type size_t.

element_index_type libsemigroups::FroidurePinBase::product_by_reduction(element_index_type i, element_index_type j) const

Compute a product using the Cayley graph.

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

Complexity

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

Parameters

  • i – the first index of an element

  • j – the second index of an element

Throws

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

Returns

A value of type element_index_type.