Member functions and types inherited from CongruenceInterface¶
This page contains a description of the member functions of the KnuthBendix
class inherited from CongruenceInterface
.
-
inline void libsemigroups::congruence::KnuthBendix::add_pair(std::initializer_list<size_t> l, std::initializer_list<size_t> r)¶
Add a generating pair to the congruence.
-
void libsemigroups::congruence::KnuthBendix::add_pair(word_type const &u, word_type const &v)¶
Add a generating pair to the congruence.
- Complexity
Linear in
u.size() + v.size()
.
Note
In some circumstances this function does not do anything. These are:
if
u
andv
are identical wordsif
has_parent_froidure_pin()
returnstrue
and the wordsu
andv
represent the same element ofparent_froidure_pin()
.
- Parameters
u – a word (vector of integers) over the generators of the semigroup.
v – a word (vector of integers) over the generators of the semigroup.
- Throws
LibsemigroupsException – if the number of generators has not yet been set via set_number_of_generators()
LibsemigroupsException – if
u
orv
contains a letter that is out of bounds.LibsemigroupsException – if started() returns
true
indicating that the underlying algorithm has been applied (partially or fully) to the data structure.
- Returns
(None)
-
inline const_iterator libsemigroups::congruence::KnuthBendix::cbegin_generating_pairs() const noexcept¶
Returns a const iterator pointing to the first generating pair.
- Complexity
Constant.
- Parameters
(None)
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A const_iterator pointing to a relation_type.
-
inline non_trivial_class_iterator libsemigroups::congruence::KnuthBendix::cbegin_ntc()¶
Returns a const iterator pointing to the first non-singleton class.
- Complexity
See warnings.
- Parameters
(None)
Warning
The problem of determining the return value of this function is undecidable in general, and this function may never terminate.
- Throws
LibsemigroupsException – if has_parent_froidure_pin() returns
false
.- Returns
A non_trivial_class_iterator pointing to a std::vector<word_type>.
-
inline const_iterator libsemigroups::congruence::KnuthBendix::cend_generating_pairs() const noexcept¶
Returns a const iterator pointing one-after-the-end of the last generating pair.
- Complexity
Constant.
- Parameters
(None)
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A const_iterator pointing to a relation_type.
-
inline non_trivial_class_iterator libsemigroups::congruence::KnuthBendix::cend_ntc()¶
Returns a const iterator pointing one-past-the-end of the last non-singleton class.
- Complexity
See warnings.
- Parameters
(None)
Warning
The problem of determining the return value of this function is undecidable in general, and this function may never terminate.
- Throws
LibsemigroupsException – if has_parent_froidure_pin() returns
false
.- Returns
A non_trivial_class_iterator pointing to a std::vector<word_type>.
-
word_type libsemigroups::congruence::KnuthBendix::class_index_to_word(class_index_type i)¶
Get a canonical representative of the
i-th
class.If the congruence, that an object of this type represents, is defined over a semigroup with generators \(A\), then this function defines a injective function from \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if
this
has infinitely many classes, to a fixed set of words over \(A\) representing distinct congruences classes.- Complexity
See warning.
Note
word_to_class_index() and class_index_to_word() are mutually inverse functions.
Warning
The function for finding the structure of a congruence may be non-deterministic, or undecidable, and this function may never return a result.
- Parameters
i – the index of the class whose representative we want to find, a value of type word_type.
- Throws
LibsemigroupsException – if the specified class index
i
exceeds the total number of classes.std::bad_alloc – if the (possibly infinite) computation uses all the available memory.
- Returns
The word representing the
i-th
class of the congruence
-
using libsemigroups::congruence::KnuthBendix::class_index_type = size_t¶
Type for indices of congruence class indices.
-
virtual tril libsemigroups::congruence::KnuthBendix::const_contains(word_type const&, word_type const&) const override¶
Check if a pair of words is known to belong to the congruence.
- Complexity
Linear in
u.size() + v.size()
.
- Parameters
u – a word (vector of integers) over the generators of the semigroup.
v – a word (vector of integers) over the generators of the semigroup.
- Throws
LibsemigroupsException – if
u
orv
contains a letter that is out of bounds.- Returns
tril::TRUE if the words
u
andv
are known to belong to the same congruence classtril::FALSE if the words are known to not belong to the same congruence class
tril::unknown otherwise.
-
using libsemigroups::congruence::KnuthBendix::const_iterator = std::vector<relation_type>::const_iterator¶
Type for a
const_iterator
to the generating pairs.See also
-
virtual bool libsemigroups::congruence::KnuthBendix::contains(word_type const&, word_type const&) override¶
Check if a pair of words belongs to the congruence.
- 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 (vector of integers) over the generators of the semigroup.
v – a word (vector of integers) over the generators of the semigroup.
- Throws
LibsemigroupsException – if
u
orv
contains a letter that is out of bounds.std::bad_alloc – if the (possibly infinite) computation uses all the available memory.
- Returns
true
if the wordsu
andv
belong to the same congruence class, andfalse
otherwise.
-
bool libsemigroups::congruence::KnuthBendix::has_parent_fpsemigroup() const noexcept¶
Check if the congruence was constructed from a FpSemigroupInterface instance.
Returns
true
if the congruence represented bythis
was created from an FpSemigroupInterface instance.If
true
is returned, thenthis
is a congruence over a semigroup represented by an FpSemigroupInterface instance.- Complexity
Constant.
- Parameters
(None)
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A
bool
.
-
bool libsemigroups::congruence::KnuthBendix::has_parent_froidure_pin() const noexcept¶
Check if the congruence was constructed from a FroidurePin instance.
Returns
true
if the congruence represented bythis
was created from a FroidurePin instance.If
true
is returned, thenthis
is a congruence over a semigroup represented by a FroidurePin instance.- Complexity
Constant.
- Parameters
(None)
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A
bool
.
-
inline bool libsemigroups::congruence::KnuthBendix::has_quotient_froidure_pin() const noexcept¶
Check if the quotient semigroup has been computed.
Returns
true
if the congruence represented by this object knows an isomorphic quotient semigroup represented by an instance of FroidurePin.- Complexity
Constant.
- Parameters
(None)
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A
bool
.
-
bool libsemigroups::congruence::KnuthBendix::is_quotient_obviously_finite()¶
Deterministically check if the quotient is finite.
Return
true
if the number of classes in the congruence represented bythis
is obviously finite, andfalse
if it is not obviously finite.See also
- 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 there are finitely many classes in the congruence, iffalse
is returned, then the number of classes can be finite or infinite.- Throws
(None) – This function throws if the implementation throws.
- Returns
A
bool
.
-
bool libsemigroups::congruence::KnuthBendix::is_quotient_obviously_infinite()¶
Deterministically check if the quotient is infinite.
Return
true
if the number of classes in the congruence represented bythis
is obviously infinite, andfalse
if it is not obviously infinite.See also
- 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 there are infinitely many classes in the congruence, iffalse
is returned, then the number of classes can be finite or infinite.- Throws
(None) – This function throws if the implementation throws.
- Returns
A
bool
.
-
inline congruence_kind libsemigroups::congruence::KnuthBendix::kind() const noexcept¶
The handedness of the congruence (left, right, or 2-sided).
- Complexity
Constant.
- Parameters
(None)
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
-
inline virtual bool libsemigroups::congruence::KnuthBendix::less(word_type const &u, word_type const &v)¶
Compare the indices of the classes containing two words.
This function returns
true
if the congruence class ofv
is less than the class ofv
in a total ordering of congruence classes.- Complexity
See warning.
- Possible Implementation
bool less(word_type const& u, word_type const& v) { return word_to_class_index(u) < word_to_class_index(v); }
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 (vector of integers) over the generators of the semigroup.
v – a word (vector of integers) over the generators of the semigroup.
- Throws
LibsemigroupsException – if
u
orv
contains a letter that is out of bounds.std::bad_alloc – if the (possibly infinite) computation uses all the available memory.
- Returns
true
if the class ofu
is less than that of.
-
using libsemigroups::congruence::KnuthBendix::non_trivial_class_iterator = non_trivial_classes_type::const_iterator¶
Type for a
const_iterator
to non-trivial classes.See also
cbegin_ntc and cend_ntc.
-
inline std::shared_ptr<non_trivial_classes_type const> libsemigroups::congruence::KnuthBendix::non_trivial_classes()¶
Returns a shared pointer to the non-trivial classes.
- Returns
-
using libsemigroups::congruence::KnuthBendix::non_trivial_classes_type = std::vector<std::vector<word_type>>¶
Type for non-trivial classes.
See also
cbegin_ntc and cend_ntc.
-
size_t libsemigroups::congruence::KnuthBendix::number_of_classes()¶
Compute the number of classes in the congruence.
- Complexity
See warning.
- Parameters
(None)
Warning
The problem of determining the number of classes of a congruence over a finitely presented semigroup is undecidable in general, and this function may never terminate.
- Throws
std::bad_alloc – if the (possibly infinite) computation uses all the available memory.
- Returns
The number of congruences classes of
this
if this number is finite, or POSITIVE_INFINITY in some cases ifthis
number is not finite.
-
inline size_t libsemigroups::congruence::KnuthBendix::number_of_generating_pairs() const noexcept¶
The number of generating pairs.
This function returns the number of generating pairs of the congruence.
See also
- Complexity
Constant.
- Parameters
(None)
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A value of type
size_t
.
-
inline size_t libsemigroups::congruence::KnuthBendix::number_of_generators() const noexcept¶
The number of generators.
This function returns the number of generators of the semigroup of the congruence that an object of this type represents, or UNDEFINED if this has not been defined.
See also
- Complexity
Constant.
- Parameters
(None)
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A value of type
size_t
.
-
inline size_t libsemigroups::congruence::KnuthBendix::number_of_non_trivial_classes()¶
The number of non-singleton classes.
- 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
LibsemigroupsException – if has_parent_froidure_pin() returns
false
.- Returns
The number of non-singleton classes of the congruence.
-
std::shared_ptr<FpSemigroupInterface> libsemigroups::congruence::KnuthBendix::parent_fpsemigroup() const¶
Get the parent FpSemigroupInterface instance (if any).
Returns a std::shared_ptr to the parent FpSemigroupInterface object over which the congruence represented by this object was defined, if it exists.
- Complexity
Constant.
- Parameters
(None)
- Throws
LibsemigroupsException – if
this
was not created using a FpSemigroupInterface instance.- Returns
A std::shared_ptr to an FpSemigroupInterface.
-
std::shared_ptr<FroidurePinBase> libsemigroups::congruence::KnuthBendix::parent_froidure_pin() const¶
Get the parent FroidurePin instance (if any).
Returns a std::shared_ptr to the parent FroidurePin over which the congruence represented by this object was defined, if it exists.
- Complexity
Constant.
- Parameters
(None)
- Throws
LibsemigroupsException – if
this
was not created using a FroidurePin instance.- Returns
-
std::shared_ptr<FroidurePinBase> libsemigroups::congruence::KnuthBendix::quotient_froidure_pin()¶
Returns a semigroup represented as an instance of a derived class of FroidurePinBase that is isomorphic to the quotient of the parent semigroup of
this
by the 2-sided congruence thatthis
represents.- Parameters
(None)
Note
The returned FroidurePin instance satisfies
FroidurePin::immutable() == true
and so certain of its member functions (those that change the underlying mathematical object) are disabled.Warning
The problem of determining the return value of this function is undecidable in general, and this function may never terminate.
- Throws
LibsemigroupsException – if any of the following hold:
the congruence is not 2-sided,
side() != congruence_kind::twosided
the quotient semigroup is known (or can be easily be shown to be) infinite
the implementation throws.
std::bad_alloc – if the (possibly infinite) computation uses all the available memory.
- Returns
-
void libsemigroups::congruence::KnuthBendix::set_number_of_generators(size_t n)¶
Set the number of generators of the congruence.
- Complexity
Constant.
- Parameters
n – the number of generators.
- Throws
LibsemigroupsException – If the number of generators has already been set to another value, or the parameter
n
is 0.- Returns
(None)
-
class_index_type libsemigroups::congruence::KnuthBendix::word_to_class_index(word_type const &w)¶
Convert a word into the index of the class containing it.
If the congruence, that an object of this type represents, is defined over a semigroup with generators \(A\), then this function defines a surjective function from the set of all words over \(A\) to either \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if
this
has infinitely many classes.- Complexity
See warning.
Note
word_to_class_index() and class_index_to_word() are mutually inverse functions.
Warning
The function for finding the structure of a congruence may be non-deterministic, or undecidable, and this function may never return a result.
- Parameters
w – the word whose class index we want to find. The parameter
w
must be a word_type consisting of indices of the generators of the semigroup over whichthis
is defined.- Throws
LibsemigroupsException – if
w
contains a letter that is out of bounds, or the object has not been fully initialised.std::bad_alloc – if the (possibly infinite) computation uses all the available memory.
- Returns
The index of the congruence class corresponding to
word
.