KnuthBendixCongruenceByPairs

class KnuthBendixCongruenceByPairs : public libsemigroups::CongruenceByPairsHelper<FroidurePin<detail::KBE, FroidurePinTraits<detail::KBE, fpsemigroup::KnuthBendix>>>

Defined in cong-pair.hpp.

On this page, we describe the functionality relating to the brute force enumeration of pairs of elements belonging to a congruence (of any type) that is implemented in the class KnuthBendixCongruenceByPairs. This class is derived from CongruenceByPairs and implements the same algorithm. The only difference is that KnuthBendixCongruenceByPairs runs the Knuth-Bendix algorithm (see fpsemigroup::KnuthBendix) to completion, and then runs the brute force enumeration of pairs on the semigroup represented by the output of fpsemigroup::KnuthBendix. If the semigroup represented by the output of fpsemigroup::KnuthBendix is infinite, but the number of pairs belonging to the congruence represented by a KnuthBendixCongruenceByPairs instance is finite, then KnuthBendixCongruenceByPairs will terminate eventually, where as CongruenceByPairs would not (since it would attempt to enumerate the infinite semigroup represented by the output of fpsemigroup::KnuthBendix first).

See

congruence_type, tril, and CongruenceByPairs.

Example

fpsemigroup::KnuthBendix kb;
kb.set_alphabet(3);
kb.add_rule({0, 1}, {1, 0});
kb.add_rule({0, 2}, {2, 0});
kb.add_rule({0, 0}, {0});
kb.add_rule({0, 2}, {0});
kb.add_rule({2, 0}, {0});
kb.add_rule({1, 2}, {2, 1});
kb.add_rule({1, 1, 1}, {1});
kb.add_rule({1, 2}, {1});
kb.add_rule({2, 1}, {1});

KnuthBendixCongruenceByPairs kbp(twosided, kb);
kbp.add_pair({0}, {1});

kbp.nr_non_trivial_classes();  // == 1
kbp.cbegin_ntc()->size();      // == 5

Type aliases

Words and class indices