Properties

This page contains information about the member functions of the ToddCoxeter class that can be used to check if the table is complete and compatible with the defining relations.

bool libsemigroups::congruence::ToddCoxeter::compatible() const noexcept

Check if the table is compatible with the relations.

Returns true if the coset table is compatible with the relations and generating pairs used to create this, and false if it is not. The table is compatible if the values obtained by pushing a coset through the left-hand side and the right-hand side of a relation coincide for every coset and every relation.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type bool.

bool libsemigroups::congruence::ToddCoxeter::complete() const noexcept

Check if the table is complete.

Returns true if the coset table is complete, and false if it is not. The table is complete if the value UNDEFINED does not appear in any row of an active coset.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type bool.

size_t libsemigroups::congruence::ToddCoxeter::felsch_tree_height()

Returns the height of the Felsch tree.

This function returns the height of the Felsch tree of a ToddCoxeter instance. Processing deductions involves performing a depth first search in this tree.

Parameters

(None)

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type size_t.

size_t libsemigroups::congruence::ToddCoxeter::felsch_tree_number_of_nodes()

Returns the number of nodes of the Felsch tree.

This function returns the number of nodes in the Felsch tree of a ToddCoxeter instance. Processing deductions involves performing a depth first search in this tree.

Parameters

(None)

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type size_t.

tril libsemigroups::congruence::ToddCoxeter::is_non_trivial(size_t tries = 10, std::chrono::milliseconds try_for = std::chrono::milliseconds(100), float threshold = 0.99)

Check if the congruence has more than one class.

Returns tril::TRUE if it is possible to show that the congruence is non-trivial; tril::FALSE if the congruence is already known to be trivial; and tril::unknown if it is not possible to show that the congruence is non-trivial.

This function attempts to find a non-trivial congruence containing the congruence represented by a ToddCoxeter instance by repeating the following steps on a copy until the enumeration concludes:

  1. running the enumeration for the specified amount of time

  2. repeatedly choosing a random pair of cosets and identifying them, until the number of cosets left in the quotient is smaller than threshold times the initial number of cosets for this step. If at the end of this process, the ToddCoxeter instance is non-trivial, then the original ToddCoxeter is also non-trivial. Otherwise, the entire process is repeated again up to a total of tries times.

Parameters
  • tries – the number of attempts to find non-trivial super-congruence.

  • try_for – the amount of time in millisecond to enumerate the congruence after choosing a random pair of representatives and identifying them.

  • threshold – the threshold (see description).

Returns

A value of type tril

size_t libsemigroups::congruence::ToddCoxeter::length_of_generating_pairs()

Returns the total length of the generating pairs.

This function returns the total length of the words that make up the generating pairs and any underlying relations.

Parameters

(None)

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type size_t.

inline size_t libsemigroups::congruence::ToddCoxeter::number_of_words(class_index_type i) const

Returns the size of the specified class.

This function returns the number of words in the free semigroup that belong to the class with index i.

Warning

This function does not trigger any enumeration!

Parameters

i – the index of the class

Returns

A value of type size_t.

inline size_t libsemigroups::congruence::ToddCoxeter::number_of_words(word_type const &w)

Returns the size of the specified class.

This function returns the number of words in the free semigroup that belong to the class of the word w.

Parameters

w – a word in the class.

Returns

A value of type size_t.

std::string libsemigroups::congruence::ToddCoxeter::to_gap_string()

Returns a string containing a GAP definition of the finitely presented semigroup represented by a ToddCoxeter instance.

Parameters

(None)

Throws
Returns

A std::string.