ToddCoxeter helpers

This page contains the documentation for various helper functions for manipulating ToddCoxeter objects.

Contents

class_by_index(…)

Returns an iterator yielding every word list[int] or str in the congruence class with given index.

class_of(…)

Returns an iterator yielding every word (of the same type as w) in the congruence class of the given word w.

is_non_trivial(…)

Check if the congruence has more than one class.

non_trivial_classes(…)

Find the non-trivial classes in the partition of a list of words.

normal_forms(…)

Returns an iterator yielding normal forms.

partition(…)

Partition a list of words.

perform_lookbehind(…)

Perform a lookbehind.

redundant_rule(…)

Return a redundant rule or None.

Full API

This page contains the documentation for various helper functions for manipulating ToddCoxeter objects. All such functions are contained in the subpackage todd_coxeter.

todd_coxeter.class_by_index(tc: ToddCoxeter, n: int) → collections.abc.Iterator[list[int] | str]

Returns an iterator yielding every word list[int] or str in the congruence class with given index.

This function returns an iterator yielding every word belonging to the class with index n in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Parameters:
Returns:

A iterator yielding the class with index n.

Return type:

collections.abc.Iterator[list[int] | str]

Raises:

LibsemigroupsError – if n is greater than or equal to tc.number_of_classes().

todd_coxeter.class_of(tc: ToddCoxeter, w: list[int] | str) → collections.abc.Iterator[list[int] | str]

Returns an iterator yielding every word (of the same type as w) in the congruence class of the given word w.

This function returns an iterator yielding every word in belonging to the same class as the input word w in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Parameters:
Returns:

An iterator yielding words in the class of the input word.

Return type:

collections.abc.Iterator[list[int] | str]

Raises:

LibsemigroupsError – if any of the values in w is out of range, i.e. they do not belong to presentation().alphabet() and Presentation.throw_if_letter_not_in_alphabet raises.

todd_coxeter.is_non_trivial(tc: ToddCoxeter, tries: int, try_for: datetime.timedelta, threshold: float) → tril

Check if the congruence has more than one class.

Returns tril.true if it is possible to show that the congruence is non-trivial; tril.false if the congruence is already known to be trivial; and tril.unknown if it is not possible to show that the congruence is non-trivial. This function attempts to find a non-trivial congruence containing the congruence represented by a ToddCoxeter instance.

Parameters:

  • tc (ToddCoxeter) – the ToddCoxeter instance.

  • tries (int) – the number of attempts to find a non-trivial super-congruence (default: 10).

  • try_for (datetime.timedelta) – the amount of time to enumerate the congruence after choosing a random pair of representatives and identifying them (default: 100 milliseconds).

  • threshold (float) – the threshold (default: 0.99).

Returns:

Whether or not a non-trivial quotient was found.

Return type:

tril

todd_coxeter.non_trivial_classes(tc: ToddCoxeter, words: list[list[int] | str]) → list[list[list[int]] | list[str]]

Find the non-trivial classes in the partition of a list of words.

This function returns the classes with size at least \(2\) in the partition of the words in the list words induced by the ToddCoxeter instance tc.

Parameters:
Returns:

The partition of the input list.

Return type:

list[list[list[int]] | list[str]]

Raises:

LibsemigroupsError – if the number of classes in tc is infinite. In this case, the enumeration of tc will not terminate successfully.

todd_coxeter.normal_forms(tc: ToddCoxeter) → collections.abc.Iterator[str | list[int]]

Returns an iterator yielding normal forms.

This function returns an iterator yielding normal forms of the classes of the congruence represented by an instance of ToddCoxeter.

The order of the classes, and the normal forms, that are returned are controlled by ToddCoxeter.standardize. This function triggers a full enumeration of tc.

Parameters:

tc (ToddCoxeter) – the ToddCoxeter instance.

Returns:

An iterator yielding normal forms.

Return type:

collections.abc.Iterator[str | list[int]]

Raises:

LibsemigroupsError – if the number of classes in tc is infinite. In this case, the enumeration of tc will not terminate successfully.

todd_coxeter.partition(tc: ToddCoxeter, words: list[list[int] | str]) → list[list[list[int]] | list[str]]

Partition a list of words.

This function returns the classes in the partition of the words in the input list words induced by the ToddCoxeter instance tc. This function triggers a full enumeration of tc.

Parameters:
Returns:

The partitioned list of words.

Return type:

list[list[list[int]] | list[str]]

Raises:

LibsemigroupsError – if the number of classes in tc is infinite. In this case, the enumeration of tc will not terminate successfully.

todd_coxeter.perform_lookbehind(tc: ToddCoxeter) → None

Perform a lookbehind.

This function performs a “lookbehind” on the argument tc which is defined as follows. For every node n in the so-far computed WordGraph (obtained from ToddCoxeter.current_word_graph) we use the current word graph to rewrite the current short-lex least path from the initial node to n. If this rewritten word is not equal to the original word, and it also labels a path from the initial node in the current word graph to a node m, then m and n represent the same congruence class. Thus we may collapse m and n (i.e. quotient the word graph by the least congruence containing the pair m and n).

The intended use case for this function is when you have a large word graph in a partially enumerated ToddCoxeter instance, and you would like to minimise this word graph as far as possible.

For example, if we take the following monoid presentation of B. H. Neumann for the trivial group:

p = Presentation("abcdef")
p.contains_empty_word(true)
presentation.add_inverse_rules(p, "defabc")
presentation.add_rule(p, "bbdeaecbffdbaeeccefbccefb", "")
presentation.add_rule(p, "ccefbfacddecbffaafdcaafdc", "")
presentation.add_rule(p, "aafdcdbaeefacddbbdeabbdea", "")
tc = ToddCoxeter(congruence_kind.twosided, p)

Then running tc will simply grow the underlying word graph until your computer runs out of memory. The authors of libsemigroups were not able to find any combination of the many settings for ToddCoxeter where running tc returned an answer. We also tried with GAP and ACE but neither of these seemed able to return an answer either. But doing the following:

tc.lookahead_extent(options.lookahead_extent.full)
  .lookahead_style(options.lookahead_style.felsch)

tc.run_for(timedelta(seconds=1))
tc.perform_lookahead(True)
todd_coxeter.perform_lookbehind(tc)
tc.run_for(timedelta(seconds=1))
todd_coxeter.perform_lookbehind(tc)
tc.perform_lookahead(True)
tc.number_of_classes() # returns 1

returns the correct answer in about 22 seconds (on a 2024 Macbook Pro M4 Pro).

Parameters:

tc (ToddCoxeter) – the ToddCoxeter instance.

todd_coxeter.redundant_rule(p: Presentation, t: datetime.timedelta) → tuple[list[int], list[int]] | tuple[str, str] | None

Return a redundant rule or None.

Starting with the last rule in the presentation, this function attempts to run the Todd-Coxeter algorithm on the rules of the presentation except for a given omitted rule. For every such omitted rule, Todd-Coxeter is run for the length of time indicated by the second parameter t, and then it is checked if the omitted rule can be shown to be redundant. If the omitted rule can be shown to be redundant in this way, then this rule is returned. If no rule can be shown to be redundant in this way, then None is returned.

Parameters:
Returns:

A redundant rule or None.

Return type:

tuple[list[int], list[int]] | tuple[str, str] | None