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
; orrel.first
orrel.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
; orrel.first
orrel.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
; oru
orv
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
; oru
orv
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
; oru
orv
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 toalphabet().size()
; orstarted() 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
i
th 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
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.
Warning
The problem of determining the return value of this function is undecidable in general, and this function may never terminate.
- Parameters
- Throws
LibsemigroupsException – if
u
orv
contains a letter that is out of bounds.- Returns
true
if the wordsu
andv
represent the same element of the finitely presented semigroup, andfalse
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
orv
contains a letter that does not belong to alphabet().(None) – This function guarantees not to throw a LibsemigroupsException.
- Returns
true
if the stringsu
andv
represent the same element of the finitely presented semigroup, andfalse
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
- Throws
LibsemigroupsException – if
u
orv
contains a letter that is out of bounds.- Returns
true
if the wordsu
andv
represent the same element of the finitely presented semigroup, andfalse
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 bythis
has already been computed, andfalse
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 andfalse
if it has not.See also
set_identity(std::string const&) and set_identity(letter_type).
- 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).
See also
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 bythis
is obviously finite, andfalse
if it is not obviously finite.See also
- 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, iffalse
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 bythis
is obviously infinite, andfalse
if it is not obviously infinite.See also
- 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, iffalse
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
andv
represent the same element of the finitely presented semigroup represented bythis
, thennormal_form(u)
is guaranteed to equalnormal_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 thatthis
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
andv
represent the same element of the finitely presented semigroup represented bythis
, thennormal_form(u)
is guaranteed to equalnormal_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.See also
- 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
andv
represent the same element of the finitely presented semigroup represented bythis
, thennormal_form(u)
is guaranteed to equalnormal_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 thatthis
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.
See also
- 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
is0
.- Returns
(None)
-
void libsemigroups::fpsemigroup::KnuthBendix::set_alphabet(std::string const &a)¶
Set the alphabet of the finitely presented semigroup.
See also
- 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 ina
.- 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 thatid
is the identity. This function can be called repeatedly.See also
- 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 thatid
is the identity. This function can be called repeatedly.See also
- 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, orid
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 indexi
is the inverse of the letter in alphabet() with indexi
.See also
- 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 bythis
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 ofthis
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