Numbers of classes, and comparisons¶
This page contains information about the member functions of the CongruenceInterface
class for comparing words, checking membership, and counting the number of classes of several types.
-
virtual tril libsemigroups::CongruenceInterface::const_contains(word_type const &u, word_type const &v) const¶
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.
-
inline virtual bool libsemigroups::CongruenceInterface::contains(word_type const &u, word_type const &v)¶
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.
-
inline virtual bool libsemigroups::CongruenceInterface::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.
-
inline std::shared_ptr<non_trivial_classes_type const> libsemigroups::CongruenceInterface::non_trivial_classes()¶
Returns a shared pointer to the non-trivial classes.
- Returns
-
size_t libsemigroups::CongruenceInterface::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::CongruenceInterface::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.