Member functions and types inherited from FpSemigroupInterface¶
This page contains a description of the member functions of the fpsemigroup::Kambites
class inherited from FpSemigroupInterface
.
-
inline void libsemigroups::fpsemigroup::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::const_iterator = std::vector<rule_type>::const_iterator¶
Type for const iterators to the defining rules.
-
inline bool libsemigroups::fpsemigroup::Kambites::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.
-
inline virtual bool libsemigroups::fpsemigroup::Kambites::equal_to(string_type const &u, string_type const &v) 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
.LibsemigroupsException – if the small overlap class is not at least \(4\).
- Returns
true
if the stringsu
andv
represent the same element of the finitely presented semigroup, andfalse
otherwise.
-
virtual bool libsemigroups::fpsemigroup::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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 string_type libsemigroups::fpsemigroup::Kambites::normal_form(string_type 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.LibsemigroupsException – if the small overlap class is not at least \(4\).
- Returns
The normal form of the parameter
w
, a value of type std::string.
-
virtual word_type libsemigroups::fpsemigroup::Kambites::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::Kambites::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::Kambites::rule_type = std::pair<string_type, string_type>¶
Type for rules.
-
void libsemigroups::fpsemigroup::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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)
-
inline virtual uint64_t libsemigroups::fpsemigroup::Kambites::size() override¶
Returns the size of the finitely presented semigroup.
- Complexity
See warning.
- Parameters
(None)
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
.LibsemigroupsException – if the small overlap class is not at least \(4\).
- 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::Kambites::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::Kambites::string_type = std::string¶
The type of strings used by a Kambites instance.
-
std::string libsemigroups::fpsemigroup::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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::Kambites::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