Member functions and types inherited from FpSemigroupInterface¶

This page contains a description of the member functions and types of the FpSemigroup class inherited from FpSemigroupInterface.

inline void libsemigroups::fpsemigroup::KnuthBendix::add_rule(relation_type rel)¶

Add a rule using a relation_type.

Complexity: Constant.

Parameters

rel – the rule being added.

Throws

LibsemigroupsException – if any of the following apply:

started() returns true; or
rel.first or rel.second contains a letter that is out of bounds.

Returns

(None)

inline void libsemigroups::fpsemigroup::KnuthBendix::add_rule(rule_type rel)¶

Add a rule using a rule_type.

Complexity: Constant.

Parameters

rel – the rule being added.

Throws

LibsemigroupsException – if any of the following apply:

started() returns true; or
rel.first or rel.second contains a letter that is out of bounds.

Returns

(None)

inline void libsemigroups::fpsemigroup::KnuthBendix::add_rule(std::initializer_list<size_t> u, std::initializer_list<size_t> v)¶

Add a rule using two word_type const references.

Complexity: Constant.

Parameters

u – the left-hand side of the rule being added.
v – the right-hand side of the rule being added.

Throws

LibsemigroupsException – if any of the following apply:

started() returns true; or
u or v contains a letter that is out of bounds.

Returns

(None)

inline void libsemigroups::fpsemigroup::KnuthBendix::add_rule(std::string const &u, std::string const &v)¶

Add a rule using two std::string const references.

Complexity: Constant.

Parameters

u – the left-hand side of the rule being added.
v – the right-hand side of the rule being added.

Throws

LibsemigroupsException – if any of the following apply:

started() returns true; or
u or v contains a letter that does not belong to alphabet().

Returns

(None)

inline void libsemigroups::fpsemigroup::KnuthBendix::add_rule(word_type const &u, word_type const &v)¶

Add a rule using two word_type const references.

Complexity: Constant.

Parameters

u – the left-hand side of the rule being added.
v – the right-hand side of the rule being added.

Throws

LibsemigroupsException – if any of the following apply:

started() returns true; or
u or v contains a letter that is out of bounds.

Returns

(None)

void libsemigroups::fpsemigroup::KnuthBendix::add_rules(FroidurePinBase &S)¶

Add rules from a FroidurePin instance.

Complexity: At most \(O(|S||A|)\) where \(A\) is a generating set for S.

Parameters

S – a FroidurePin object representing a semigroup.

Throws

LibsemigroupsException – if any of the following apply:

alphabet() is empty;
the number of generators of S is not equal to alphabet().size(); or
started() returns true;

Returns

(None)

inline void libsemigroups::fpsemigroup::KnuthBendix::add_rules(std::vector<rule_type> const &rels)¶

Add rules in a vector.

Complexity: \(O(n)\) where \(n\) is the size of rels.

Parameters: rels – a vector of rule_type.
Throws: LibsemigroupsException – if add_rule() with argument any item in rels throws.
Returns: (None)

inline std::string const &libsemigroups::fpsemigroup::KnuthBendix::alphabet() const noexcept¶

Returns a const reference to the alphabet.

Complexity: Constant.
Parameters: (None)

Throws: (None) – This function is noexcept and is guaranteed never to throw.
Returns: A const reference to the alphabet, a value of type std::string.

inline std::string libsemigroups::fpsemigroup::KnuthBendix::alphabet(size_t i) const¶

Returns the ith letter of the alphabet.

Complexity: Constant.

Parameters: i – the index of the letter.
Throws: std::range_error – if the index i is out of range.
Returns: A std::string by value.

inline const_iterator libsemigroups::fpsemigroup::KnuthBendix::cbegin_rules() const noexcept¶

Returns an iterator pointing to the first rule.

Complexity: Constant.
Parameters: (None)

Throws: (None) – This function is noexcept and is guaranteed never to throw.
Returns: A const_iterator.

inline const_iterator libsemigroups::fpsemigroup::KnuthBendix::cend_rules() const noexcept¶

Returns an iterator pointing one past the last rule.

Complexity: Constant.
Parameters: (None)

Throws: (None) – This function is noexcept and is guaranteed never to throw.
Returns: A const_iterator.

inline letter_type libsemigroups::fpsemigroup::KnuthBendix::char_to_uint(char a) const¶

Convert a char to a letter_type.

Complexity.: Constant.

Parameters: a – the string to convert.
Throws: LibsemigroupsException – if a is not in alphabet().
Returns: a letter_type.

using libsemigroups::fpsemigroup::KnuthBendix::char_type = char¶: Type for characters.

using libsemigroups::fpsemigroup::KnuthBendix::const_iterator = std::vector<rule_type>::const_iterator¶: Type for const iterators to the defining rules.

inline bool libsemigroups::fpsemigroup::KnuthBendix::equal_to(std::initializer_list<letter_type> u, std::initializer_list<letter_type> v)¶

Check if two words represent the same element.

Complexity: See warning.
See: equal_to(std::string const&, std::string const&).

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Parameters

u – a word_type consisting of indices of the generators of the finitely presented semigroup.
v – a word_type consisting of indices of the generators of the finitely presented semigroup.

Throws

LibsemigroupsException – if u or v contains a letter that is out of bounds.

Returns

true if the words u and v represent the same element of the finitely presented semigroup, and false otherwise.

virtual bool libsemigroups::fpsemigroup::KnuthBendix::equal_to(std::string const&, std::string const&) override¶

Check if two strings represent the same element.

Complexity: See warning.
See: equal_to(word_type const&, word_type const&).

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Parameters

u – a string over the alphabet of the finitely presented semigroup.
v – a string over the alphabet of the finitely presented semigroup.

Throws

LibsemigroupsException – if u or v contains a letter that does not belong to alphabet().
(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

true if the strings u and v represent the same element of the finitely presented semigroup, and false otherwise.

virtual bool libsemigroups::fpsemigroup::KnuthBendix::equal_to(word_type const &u, word_type const &v)¶

Check if two words represent the same element.

Complexity: See warning.
See: equal_to(std::string const&, std::string const&).

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Parameters

u – a word_type consisting of indices of the generators of the finitely presented semigroup.
v – a word_type consisting of indices of the generators of the finitely presented semigroup.

Throws

LibsemigroupsException – if u or v contains a letter that is out of bounds.

Returns

true if the words u and v represent the same element of the finitely presented semigroup, and false otherwise.

inline std::shared_ptr<FroidurePinBase> libsemigroups::fpsemigroup::KnuthBendix::froidure_pin()¶

Returns an isomorphic FroidurePin instance.

Returns a FroidurePin instance isomorphic to the finitely presented semigroup defined by this.

Complexity: See warning.
Parameters: (None)

Warning

The function for finding the structure of a finitely presented semigroup may be non-deterministic, or since the problem is undecidable in general, this function may never return a result.

Throws: (None) – This function guarantees not to throw a LibsemigroupsException.
Returns: A shared pointer to a FroidurePinBase.

inline bool libsemigroups::fpsemigroup::KnuthBendix::has_froidure_pin() const noexcept¶

Check if an isomorphic FroidurePin instance is known.

Returns true if a FroidurePin instance isomorphic to the finitely presented semigroup defined by this has already been computed, and false if not.

Complexity: Constant.
Parameters: (None)

Throws: (None) – This function is noexcept and is guaranteed never to throw.
Returns: A bool.

inline bool libsemigroups::fpsemigroup::KnuthBendix::has_identity() const noexcept¶

Check if an identity has been set.

This function returns true if an identity has been set and false if it has not.

Complexity: Constant.
See: set_identity(std::string const&) and set_identity(letter_type).
Parameters: (None)

Throws: (None) – This function is noexcept and is guaranteed never to throw.
Returns: A value of type bool.

std::string const &libsemigroups::fpsemigroup::KnuthBendix::identity() const¶

Returns the identity (if any).

Complexity: Constant.
Parameters: (None)

Throws: LibsemigroupsException – if no identity has been defined.
Returns: A const reference to the identity, a value of type std::string.

std::string const &libsemigroups::fpsemigroup::KnuthBendix::inverses() const¶

Returns the inverses (if any).

Complexity: Constant.
Parameters: (None)
See: set_inverses() for the meaning of the return value of this function.

Throws: LibsemigroupsException – if no identity has been defined.
Returns: A const reference to the inverses, a value of type std::string.

bool libsemigroups::fpsemigroup::KnuthBendix::is_obviously_finite()¶

Check if the finitely presented semigroup is obviously finite.

Return true if the finitely presented semigroup represented by this is obviously finite, and false if it is not obviously finite.

Exceptions: This function guarantees not to throw a LibsemigroupsException.
Complexity: Implementation specific, but this function is guaranteed to return a result. More specifically, this function will not trigger a computation that potentially never terminates.
See: is_obviously_infinite().
Parameters: (None)

Warning

If true is returned, then the finitely presented semigroup is finite, if false is returned, then the finitely presented semigroup can be finite or infinite.

Returns: A bool.

bool libsemigroups::fpsemigroup::KnuthBendix::is_obviously_infinite()¶

Check if the finitely presented semigroup is obviously infinite.

Return true if the finitely presented semigroup represented by this is obviously infinite, and false if it is not obviously infinite.

Exceptions: This function guarantees not to throw a LibsemigroupsException.
Complexity: Implementation specific, but this function is guaranteed to return a result. More specifically, this function will not trigger a computation that potentially never terminates.
See: is_obviously_finite().
Parameters: (None)

Warning

If true is returned, then the finitely presented semigroup is infinite, if false is returned, then the finitely presented semigroup can be finite or infinite.

Returns: A bool.

inline word_type libsemigroups::fpsemigroup::KnuthBendix::normal_form(std::initializer_list<letter_type> w)¶

Returns a normal form for a word_type.

If u and v represent the same element of the finitely presented semigroup represented by this, then normal_form(u) is guaranteed to equal normal_form(v). No further guarantees are given, the return value of normal_form() depends on the implementation and may vary between finitely presented semigroups defined in precisely the same way.

Complexity: See warning.
See: normal_form(std::string const&) and normal_form(std::initializer_list<letter_type>).

Warning

The function for finding the structure of a finitely presented semigroup may be non-deterministic, or since the problem is undecidable in general, this function may never return a result.

Parameters: w – the word whose normal form we want to find. The parameter w must be a word_type consisting of indices of the generators of the finitely presented semigroup that this represents.
Throws: LibsemigroupsException – if w contains a letter that is out of bounds, or the object has not been fully initialised.
Returns: The normal form of the parameter w, a value of type word_type.

virtual std::string libsemigroups::fpsemigroup::KnuthBendix::normal_form(std::string const &w) override¶

Returns a normal form for a string.

If u and v represent the same element of the finitely presented semigroup represented by this, then normal_form(u) is guaranteed to equal normal_form(v). No further guarantees are given, the return value of normal_form() depends on the implementation and may vary between finitely presented semigroups defined in precisely the same way.

Complexity: See warning.
See: normal_form(word_type const&).

Warning

The function for finding the structure of a finitely presented semigroup may be non-deterministic, or since the problem is undecidable in general, this function may never return a result.

Parameters: w – the word whose normal form we want to find. The parameter w must be a std::string consisting of letters in alphabet().
Throws: LibsemigroupsException – if w contains a letter that is not in alphabet(), or the object has not been fully initialised.
Returns: The normal form of the parameter w, a value of type std::string.

virtual word_type libsemigroups::fpsemigroup::KnuthBendix::normal_form(word_type const &w)¶

Returns a normal form for a word_type.

If u and v represent the same element of the finitely presented semigroup represented by this, then normal_form(u) is guaranteed to equal normal_form(v). No further guarantees are given, the return value of normal_form() depends on the implementation and may vary between finitely presented semigroups defined in precisely the same way.

Complexity: See warning.
See: normal_form(std::string const&) and normal_form(std::initializer_list<letter_type>).

Warning

The function for finding the structure of a finitely presented semigroup may be non-deterministic, or since the problem is undecidable in general, this function may never return a result.

Parameters: w – the word whose normal form we want to find. The parameter w must be a word_type consisting of indices of the generators of the finitely presented semigroup that this represents.
Throws: LibsemigroupsException – if w contains a letter that is out of bounds, or the object has not been fully initialised.
Returns: The normal form of the parameter w, a value of type word_type.

inline size_t libsemigroups::fpsemigroup::KnuthBendix::number_of_rules() const noexcept¶

Returns the number of rules.

Complexity: Constant.
Parameters: (None)

Throws: (None) – This function is noexcept and is guaranteed never to throw.
Returns: A value of type size_t.

using libsemigroups::fpsemigroup::KnuthBendix::rule_type = std::pair<string_type, string_type>¶: Type for rules.

void libsemigroups::fpsemigroup::KnuthBendix::set_alphabet(size_t n)¶

Set the size of the alphabet.

Use this to specify the alphabet of a finitely presented semigroup if you intend to use indices rather than the actual letters in the alphabet in subsequent calculations.

Complexity: Constant.
See: alphabet() and set_alphabet(std::string const&).

Parameters: n – the number of letters.
Throws: LibsemigroupsException – If the size of the of alphabet has already been set to another value, or the parameter n is 0.
Returns: (None)

void libsemigroups::fpsemigroup::KnuthBendix::set_alphabet(std::string const &a)¶

Set the alphabet of the finitely presented semigroup.

Complexity: Constant.
See: alphabet() and set_alphabet(size_t).

Parameters: a – the alphabet.
Throws: LibsemigroupsException – If the alphabet has already been set to another value, the parameter a is empty, or there are repeated characters in a.
Returns: (None)

inline void libsemigroups::fpsemigroup::KnuthBendix::set_identity(letter_type id)¶

Set a character in alphabet() to be the identity using its index.

This function adds rules to this so that id is the identity. This function can be called repeatedly.

Complexity: \(O(n)\) where \(n\) is alphabet().size().
See: set_identity(std::string const&).

Parameters: id – the index of the character to be the identity.
Throws: LibsemigroupsException – If id is out of bounds.
Returns: (None)

void libsemigroups::fpsemigroup::KnuthBendix::set_identity(std::string const &id)¶

Set a character in alphabet() to be the identity.

This function adds rules to this so that id is the identity. This function can be called repeatedly.

Complexity: \(O(n)\) where \(n\) is alphabet().size().
See: set_identity(letter_type).

Parameters: id – a string containing the character to be the identity.
Throws: LibsemigroupsException – If id has length greater than 1, or id contains a character that is not in alphabet().
Returns: (None)

void libsemigroups::fpsemigroup::KnuthBendix::set_inverses(std::string const &a)¶

Set the inverses of letters in alphabet().

The letter in a with index i is the inverse of the letter in alphabet() with index i.

Complexity: \(O(n)\) where \(n\) is alphabet().size().
See: set_identity(std::string const&).

Parameters

a – a string of length alphabet().size().

Throws

LibsemigroupsException – if any of the following apply:

a is empty;
alphabet() is empty;
no identity has been defined using set_identity();
the length of a is not equal to alphabet().size();
the letters in a are not exactly those in alphabet() (perhaps in a different order).

Returns

(None)

virtual uint64_t libsemigroups::fpsemigroup::KnuthBendix::size() override¶

Returns the size of the finitely presented semigroup.

Complexity: See warning.
Parameters: (None)

Note

If this has been run until finished, then this function can determine the size of the semigroup represented by this even if it is infinite. Moreover, the complexity of this function is at worst \(O(mn)\) where \(m\) is the number of letters in the alphabet, and \(n\) is the number of nodes in the gilman_digraph.

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Throws: (None) – This function guarantees not to throw a LibsemigroupsException.
Returns: A uint64_t, the value of which equals the size of this if this number is finite, or POSITIVE_INFINITY in some cases if this number is not finite.

word_type libsemigroups::fpsemigroup::KnuthBendix::string_to_word(std::string const &w) const¶

Convert a string to a word_type.

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

Parameters: w – the string to convert.
Throws: LibsemigroupsException – if w contains any characters not in alphabet().
Returns: a word_type.

using libsemigroups::fpsemigroup::KnuthBendix::string_type = std::string¶: Type for strings.

std::string libsemigroups::fpsemigroup::KnuthBendix::to_gap_string()¶

Returns a string containing GAP commands for defining a finitely presented semigroup.

Complexity: \(O(m + n)\) where \(m\) is alphabet().size() and \(n\) is number_of_rules().
Parameters: (None)

Throws: (None) – This function guarantees not to throw a LibsemigroupsException.
Returns: A std::string.

inline char libsemigroups::fpsemigroup::KnuthBendix::uint_to_char(letter_type a) const¶

Convert a letter_type to a char.

Complexity.: Constant.

Parameters: a – the letter_type to convert.
Throws: LibsemigroupsException – if a is out of range.
Returns: A char.

void libsemigroups::fpsemigroup::KnuthBendix::validate_letter(char c) const¶

Validates a letter specified by a char.

Complexity: Constant.
Parameters: (None)

Parameters: c – the letter to validate.
Throws: LibsemigroupsException – if c does not belong to alphabet().
Returns: (None)

void libsemigroups::fpsemigroup::KnuthBendix::validate_letter(letter_type c) const¶

Validates a letter specified by an integer.

Complexity: Constant.
Parameters: (None)

Parameters: c – the letter to validate.
Throws: LibsemigroupsException – if c is out of range.
Returns: (None)

inline void libsemigroups::fpsemigroup::KnuthBendix::validate_word(std::string const &w) const¶

Validates a word given by a std::string.

Complexity: Linear in the length of w.
Parameters: (None)

Parameters: w – the word to validate.
Throws: LibsemigroupsException – if any character in w does not belong to alphabet().
Returns: (None)

inline void libsemigroups::fpsemigroup::KnuthBendix::validate_word(word_type const &w) const¶

Validates a word given by a word_type.

Complexity: Linear in the length of w.
Parameters: (None)

Parameters: w – the word to validate.
Throws: LibsemigroupsException – if any index in w is out of range.
Returns: (None)

std::string libsemigroups::fpsemigroup::KnuthBendix::word_to_string(word_type const &w) const¶

Convert a word_type to a std::string.

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

Parameters: w – the word_type to convert.
Throws: LibsemigroupsException – if w contains any indices that are out of range.
Returns: a std::string