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