The ToddCoxeter class
Class containing an implementation of the Todd-Coxeter Algorithm.
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.
Important
The class ToddCoxeter has all the methods of the Runner class but, for
boring technical reasons, is not a subclass of Runner. If thing is
an instance of ToddCoxeter, then you can use thing as if it were an instance
of Runner but isinstance(thing, Runner) will return False.
>>> from libsemigroups_pybind11 import (presentation, Presentation, ToddCoxeter,
... congruence_kind, word_graph, Order, todd_coxeter)
>>> tc = ToddCoxeter(word=str)
>>> options = tc.options
>>> p = Presentation("ab")
>>> p.contains_empty_word(True)
<monoid presentation with 2 letters, 0 rules, and length 0>
>>> presentation.add_rule(p, "aa", "")
>>> presentation.add_rule(p, "a", "b")
>>> tc.init(congruence_kind.onesided, p).strategy(options.strategy.felsch)
<1-sided ToddCoxeter over <monoid presentation with 2 letters, 2 rules, and length 4> with 0 gen. pairs + 1 node>
>>> tc.number_of_classes()
2
>>> tc.contains("aaaa", "aa")
True
>>> tc.index_of("aaaa")
0
>>> p = Presentation("abcd")
>>> presentation.add_rule(p, "aa", "a");
>>> presentation.add_rule(p, "ba", "b");
>>> presentation.add_rule(p, "ab", "b");
>>> presentation.add_rule(p, "ca", "c");
>>> presentation.add_rule(p, "ac", "c");
>>> presentation.add_rule(p, "da", "d");
>>> presentation.add_rule(p, "ad", "d");
>>> presentation.add_rule(p, "bb", "a");
>>> presentation.add_rule(p, "cd", "a");
>>> presentation.add_rule(p, "ccc", "a");
>>> presentation.add_rule(p, "bcbcbcbcbcbcbc", "a");
>>> presentation.add_rule(p, "bcbdbcbdbcbdbcbdbcbdbcbdbcbdbcbd", "a");
>>> tc = ToddCoxeter(congruence_kind.twosided, p)
>>> tc.strategy(options.strategy.hlt).lookahead_extent(options.lookahead_extent.partial).save(False)
<2-sided ToddCoxeter over <semigroup presentation with 4 letters, 12 rules, and length 79> with 0 gen. pairs + 1 node>
>>> tc.number_of_classes()
10752
>>> tc
<2-sided ToddCoxeter over <semigroup presentation with 4 letters, 12 rules, and length 79> with 0 gen. pairs + 10,753 nodes>
>>> tc.word_graph()
<WordGraph with 10,753 nodes, 43,012 edges, & out-degree 4>
>>> it = todd_coxeter.normal_forms(tc)
>>> [next(it) for _ in range(10)]
['a', 'b', 'c', 'd', 'bc', 'bd', 'cb', 'db', 'bcb', 'bdb']
>>> tc.standardize(Order.lex)
True
>>> it = todd_coxeter.normal_forms(tc)
>>> [next(it) for _ in range(10)]
['a', 'ab', 'abc', 'abcb', 'abcbc', 'abcbcb', 'abcbcbc', 'abcbcbcb', 'abcbcbcbc', 'abcbcbcbcb']