ToddCoxeter class

Defined in todd-coxeter-class.hpp.

This class contains an implementation of the Todd-Coxeter algorithm for computing 1-sided (right), and 2-sided congruences on a semigroup or monoid.

In this documentation we use the term "congruence 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.

For information about the output printed by a ToddCoxeter instance during a congruence enumeration, see this page.

See also

congruence_kind and tril.

Example 1

Presentation<word_type> p;
p.alphabet(2);
presentation::add_rule(p, 00_w, 0_w);
presentation::add_rule(p, 0_w, 1_w);
ToddCoxeter tc(congruence_kind::onesided, p);
tc.strategy(options::strategy::felsch);
tc.number_of_classes();
tc.contains(0000_w, 00_w);
tc.index_of(0000_w);

Example 2

Presentation<word_type> p;
p.alphabet(4);
presentation::add_rule(p, 00_w, 0_w);
presentation::add_rule(p, 10_w, 1_w);
presentation::add_rule(p, 01_w, 1_w);
presentation::add_rule(p, 20_w, 2_w);
presentation::add_rule(p, 02_w, 2_w);
presentation::add_rule(p, 30_w, 3_w);
presentation::add_rule(p, 03_w, 3_w);
presentation::add_rule(p, 11_w, 0_w);
presentation::add_rule(p, 23_w, 0_w);
presentation::add_rule(p, 222_w, 0_w);
presentation::add_rule(p, 12121212121212_w, 0_w);
presentation::add_rule(p, 12131213121312131213121312131213_w, 0_w);
ToddCoxeter tc(congruence_kind::twosided, p);
tc.strategy(options::strategy::hlt)
   .lookahead_extent(options::lookahead_extent::partial)
   .save(false);
tc.number_of_classes()  // 10'752
tc.standardize(order::recursive);
normal_forms(tc) | rx::take(10) | rx::to_vector()
// {0_w,
//  1_w,
//  2_w,
//  21_w,
//  12_w,
//  121_w,
//  22_w,
//  221_w,
//  212_w,
//  2121_w}
tc.standardize(order::lex);
normal_forms(tc) | rx::take(10) | rx::to_vector()
// {0_w,
//  01_w,
//  012_w,
//  0121_w,
//  01212_w,
//  012121_w,
//  0121212_w,
//  01212121_w,
//  012121212_w,
//  0121212121_w};

Topics
	Member types
	Public member types.
	Constructors + initializers
	Construct or re-initialize a ToddCoxeter instance (public member function).
	Settings
	Settings that control the behaviour of a ToddCoxeter class instance.
	Common member functions
	Documentation of common member functions of Congruence, Kambites, KnuthBendix, and ToddCoxeter.
	Accessors
	Member functions that can be used to access the state of a ToddCoxeter instance.
	Modifiers
	Member functions that can be used to modify the state of a ToddCoxeter instance.
	Word to class index
	Member functions for converting a word into the index of a class in a ToddCoxeter instance.
	Class index to word
	Member functions for converting the index of a class into a word in a ToddCoxeter instance.

Functions
template<typename Word>
	ToddCoxeter (congruence_kind, Presentation< Word > &&) -> ToddCoxeter< Word >
	Deduction guide.
template<typename Word>
	ToddCoxeter (congruence_kind, Presentation< Word > const &) -> ToddCoxeter< Word >
	Deduction guide.
template<typename Word>
	ToddCoxeter (congruence_kind, ToddCoxeter< Word > const &) -> ToddCoxeter< Word >
	Deduction guide.
template<typename Node>
	ToddCoxeter (congruence_kind, WordGraph< Node > &&) -> ToddCoxeter< word_type >
	Deduction guide.
template<typename Node>
	ToddCoxeter (congruence_kind, WordGraph< Node > const &) -> ToddCoxeter< word_type >
	Deduction guide.
template<typename Word>
	ToddCoxeter (ToddCoxeter< Word > &&) -> ToddCoxeter< Word >
	Deduction guide.
template<typename Word>
	ToddCoxeter (ToddCoxeter< Word > const &) -> ToddCoxeter< Word >
	Deduction guide.

Function Documentation

ToddCoxeter() [1/7]

template<typename Word>

ToddCoxeter	(	congruence_kind	,
		Presentation< Word > &&	) -> ToddCoxeter< Word >

Defined in todd-coxeter-class.hpp.

Deduction guide to construct a ToddCoxeter<Word> from a Presentation<Word> rvalue reference.

ToddCoxeter() [2/7]

template<typename Word>

ToddCoxeter	(	congruence_kind	,
		Presentation< Word > const &	) -> ToddCoxeter< Word >

Defined in todd-coxeter-class.hpp.

Deduction guide to construct a ToddCoxeter<Word> from a Presentation<Word> const reference.

ToddCoxeter() [3/7]

template<typename Word>

ToddCoxeter	(	congruence_kind	,
		ToddCoxeter< Word > const &	) -> ToddCoxeter< Word >

Defined in todd-coxeter-class.hpp.

Deduction guide to construct a ToddCoxeter<Word> from a ToddCoxeter<Word> const reference.

ToddCoxeter() [4/7]

template<typename Node>

ToddCoxeter	(	congruence_kind	,
		WordGraph< Node > &&	) -> ToddCoxeter< word_type >

Defined in todd-coxeter-class.hpp.

Deduction guide to construct a ToddCoxeter<word_type> from a WordGraph<Node> rvalue reference.

ToddCoxeter() [5/7]

template<typename Node>

ToddCoxeter	(	congruence_kind	,
		WordGraph< Node > const &	) -> ToddCoxeter< word_type >

Defined in todd-coxeter-class.hpp.

Deduction guide to construct a ToddCoxeter<word_type> from a WordGraph<Node> const reference.

ToddCoxeter() [6/7]

template<typename Word>

ToddCoxeter

(

ToddCoxeter< Word > &&

)

-> ToddCoxeter< Word >

Defined in todd-coxeter-class.hpp.

Deduction guide to construct a ToddCoxeter<Word> from a ToddCoxeter<Word> rvalue reference.

ToddCoxeter() [7/7]

template<typename Word>

ToddCoxeter

(

ToddCoxeter< Word > const &

)

-> ToddCoxeter< Word >

Defined in todd-coxeter-class.hpp.

Deduction guide to construct a ToddCoxeter<Word> from a ToddCoxeter<Word> const reference.