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 or v contains a letter that is out of bounds.

Returns

  • tril::TRUE if the words u and v are known to belong to the same congruence class

  • tril::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 or v 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 words u and v belong to the same congruence class, and false 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 of v is less than the class of v 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 or v 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 of u 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

A std::shared_ptr to non_trivial_classes_type.

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