# 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.

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)

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)

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)

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

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.

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.

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.

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).

set_inverses() for the meaning of the return value of this function.

Complexity

Constant.

Parameters

(None)

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.

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.

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.

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.

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.

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.

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.

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().

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().

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().

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
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
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