congruence::ToddCoxeter¶
-
class ToddCoxeter : public libsemigroups::CongruenceInterface, public libsemigroups::detail::CosetManager¶
Defined in
todd-coxeter.hpp
.This class contains the main implementation of the Todd-Coxeter algorithm for computing left, right, and 2-sided congruences on semigroups and monoids.
This page contains a summary of the main member functions of the class congruence::ToddCoxeter, and related things in libsemigroups.
In this documentation we use the term “coset enumeration” to mean the execution of (any version of) the Todd-Coxeter algorithm.
Some of the features of this class were inspired by similar features in ACE by George Havas and Colin Ramsay.
See also
congruence_kind and tril.
- Example 1
ToddCoxeter tc(congruence_kind::left); // construct a left congruence tc.set_number_of_generators(2); // 2 generators tc.add_pair({0, 0}, {0}); // generator 0 squared is itself tc.add_pair({0}, {1}); // generator 0 equals 1 tc.strategy(options::strategy::felsch); // set the strategy tc.number_of_classes(); tc.contains({0, 0, 0, 0}, {0, 0}); equal tc.word_to_class_index({0, 0, 0, 0}); tc.standardize(order::lex);
- Example 2
ToddCoxeter tc(congruence_kind::twosided); tc.set_number_of_generators(4); tc.add_pair({0, 0}, {0}); tc.add_pair({1, 0}, {1}); tc.add_pair({0, 1}, {1}); tc.add_pair({2, 0}, {2}); tc.add_pair({0, 2}, {2}); tc.add_pair({3, 0}, {3}); tc.add_pair({0, 3}, {3}); tc.add_pair({1, 1}, {0}); tc.add_pair({2, 3}, {0}); tc.add_pair({2, 2, 2}, {0}); tc.add_pair({1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2}, {0}); tc.add_pair({1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3}, {0}); tc.strategy(options::strategy::hlt) .standardize(false) .lookahead(options::lookahead::partial) .save(false) tc.number_of_classes() // 10752 tc.complete(); // true tc.compatible(); // true auto& S = tc.quotient_semigroup(); // FroidurePin<TCE> S.size() // 10752 S.number_of_idempotents() // 1 tc.standardize(order::recursive); std::vector<word_type>(tc.cbegin_normal_forms(), tc.cbegin_normal_forms() + 10); // {{0}, // {1}, // {2}, // {2, 1}, // {1, 2}, // {1, 2, 1}, // {2, 2}, // {2, 2, 1}, // {2, 1, 2}, // {2, 1, 2, 1}}; tc.standardize(order::lex); std::vector<word_type>(tc.cbegin_normal_forms(), tc.cbegin_normal_forms() + 10); // {{0}, // {0, 1}, // {0, 1, 2}, // {0, 1, 2, 1}, // {0, 1, 2, 1, 2}, // {0, 1, 2, 1, 2, 1}, // {0, 1, 2, 1, 2, 1, 2}, // {0, 1, 2, 1, 2, 1, 2, 1}, // {0, 1, 2, 1, 2, 1, 2, 1, 2}, // {0, 1, 2, 1, 2, 1, 2, 1, 2, 1}};
Member types¶
The type of a const iterator pointing to a word belonging to a particular class. |
|
Type of cosets stored in the table. |
|
The type of the return value of |
|
The type of a const iterator pointing to a normal form. |
|
Holds values of various options. |
|
Values for specifying how to handle deductions. |
|
Values for specifying whether to use relations or Cayley graph. |
|
Values for specifying the type of lookahead to perform. |
|
Values for specifying how to handle preferred definitions. |
|
Values for defining the strategy. |
|
The possible arguments for |
|
Type of the argument to |
|
Type of the argument to |
|
Type of the underlying table. |
Constructors¶
Copy constructor. |
|
Construct from kind (left/right/2-sided). |
|
Construct from kind (left/right/2-sided) and |
|
Construct from kind (left/right/2-sided) and |
|
Construct from kind (left/right/2-sided) and |
|
Construct from kind (left/right/2-sided) and |
|
|
Construct from kind (left/right/2-sided), shared pointer to |
Deleted constructors¶
Deleted. |
|
Deleted. |
|
Deleted. |
|
Deleted. |
Initialization¶
Prefill the coset table. |
Settings¶
The current value of the deduction policy setting. |
|
Specify how to handle deductions. |
|
The current value of the f_defs setting. |
|
The approx number of Felsch style definitions in ACE strategies. |
|
The current value of the Froidure-Pin policy setting. |
|
Specify whether to use the relations or the Cayley graph. |
|
The current value of the hlt_defs setting. |
|
The approx number of HLT style definitions in ACE strategies. |
|
The current value of the large collapse setting. |
|
Specify what should be considered a large collapse. |
|
The current value of the setting for lookaheads. |
|
Set the style of lookahead to use in HLT. |
|
The current value of the lookahead growth factor. |
|
Set the lookahead growth factor. |
|
The current value of the lookahead growth threshold. |
|
Set the lookahead growth threshold. |
|
The current value of the lower bound setting. |
|
Specify minimum number of classes that may trigger early stop. |
|
The current value of the setting for the maximum number of deductions. |
|
The maximum number of deductions in the stack. |
|
The current value of the maximum preferred definitions setting. |
|
Specify the maximum number of preferred definitions. |
|
The current value of the minimum lookahead setting. |
|
Set the minimum value of |
|
The current value of the next lookahead setting. |
|
Set the threshold that will trigger a lookahead in HLT. |
|
The current value of the preferred definitions setting. |
|
Specify how to handle preferred definitions. |
|
The current value of the random interval setting. |
|
Set the amount of time per strategy for |
|
Set the amount of time per strategy for |
|
Randomly shuffle the generating pairs. |
|
Remove duplicate generating pairs. |
|
The current value of the restandardize setting. |
|
Specify whether to standardize between HLT and Felsch. |
|
The current value of save setting. |
|
Process deductions during HLT. |
|
Returns a string containing a tabularized summary of all the settings. |
|
Simplify defining relations and/or generating pairs. |
|
Sort generating pairs. |
|
Sort generating pairs. |
|
The current value of the standardize setting. |
|
Partially short-lex standardize the table during enumeration. |
|
The current strategy for enumeration. |
|
Specify the strategy. |
|
The current value of the setting for using relations. |
|
Perform an HLT-style push of the defining relations at the identity. |
Statistics¶
Returns a const reference to a statistics object. |
|
Returns a string containing a tabularized summary of the statistics. |
Container-like¶
Check if there are no relations or generating pairs. |
|
Reserve the specified capacity in the coset table. |
|
Release unused memory if |
Standardization¶
Check if the table has been standardized. |
|
Returns the current order in which the table is standardized. |
|
Standardize the table according to the specified order. |
Iterators¶
Returns a |
|
Returns a |
|
Returns a const iterator pointing at the first word in a generating pair. |
|
Returns a |
|
Returns a const iterator pointing at the first word in the first defining relation (if any). |
|
Returns a |
|
Returns a const iterator pointing one after the last word in any generating pair. |
|
Returns a |
|
Returns a const iterator pointing one after the last word in the last defining relation (if any). |
Properties¶
Check if the table is compatible with the relations. |
|
Check if the table is complete. |
|
Returns the height of the Felsch tree. |
|
Returns the number of nodes of the Felsch tree. |
|
Check if the congruence has more than one class. |
|
Returns the total length of the generating pairs. |
|
Returns the size of the specified class. |
|
Returns the size of the specified class. |
|
Returns a string containing a GAP definition of the finitely presented semigroup represented by a |
Member functions inherited from CosetManager¶
Returns the capacity of the coset table. |
|
Returns the first free coset. |
|
The current value of the growth factor setting. |
|
Set the value of the growth factor setting. |
|
Check if there are any free cosets. |
|
Check if the given coset is active or not. |
|
Check if the given coset is valid. |
|
Returns the next active coset after the given coset. |
|
Returns the number of active cosets. |
|
Returns the total number of cosets defined so far. |
|
Returns the total number of cosets that have been killed so far. |
Member functions inherited from CongruenceInterface¶
|
Add a generating pair to the congruence. |
Add a generating pair to the congruence. |
|
Returns a const iterator pointing to the first generating pair. |
|
Returns a const iterator pointing to the first non-singleton class. |
|
Returns a const iterator pointing one-after-the-end of the last generating pair. |
|
Returns a const iterator pointing one-past-the-end of the last non-singleton class. |
|
Get a canonical representative of the |
|
Type for indices of congruence class indices. |
|
Check if a pair of words is known to belong to the congruence. |
|
Type for a |
|
Check if a pair of words belongs to the congruence. |
|
Check if the congruence was constructed from a |
|
Check if the congruence was constructed from a |
|
Check if the quotient semigroup has been computed. |
|
Deterministically check if the quotient is finite. |
|
Deterministically check if the quotient is infinite. |
|
The handedness of the congruence (left, right, or 2-sided). |
|
Compare the indices of the classes containing two words. |
|
Type for a |
|
Returns a shared pointer to the non-trivial classes. |
|
Type for non-trivial classes. |
|
Compute the number of classes in the congruence. |
|
The number of generating pairs. |
|
The number of generators. |
|
The number of non-singleton classes. |
|
Get the parent |
|
Get the parent |
|
Returns a semigroup represented as an instance of a derived class of |
|
Set the number of generators of the congruence. |
|
Convert a word into the index of the class containing it. |
Member functions inherited from Runner¶
Check if the runner is dead. |
|
Check if |
|
Stop |
|
Check if it is time to report. |
|
Get the minimum elapsed time between reports. |
|
Set the minimum elapsed time between reports. |
|
Set the minimum elapsed time between reports. |
|
Report why |
|
Run until |
|
Run for a specified amount of time. |
|
Run for a specified amount of time. |
|
Run until a nullary predicate returns |
|
Run until a nullary predicate returns |
|
Check if currently running. |
|
Check if the runner is currently running for a particular length of time. |
|
Check if the runner is currently running until a nullary predicate returns |
|
Check if |
|
Check if the runner is stopped. |
|
Check if the runner was, or should, stop because of the argument for |
|
Check if the amount of time passed to |