Modifiers

This page contains documentation of the member functions of ToddCoxeter that can be used to modify the state of a ToddCoxeter instance. In other words, for modifying the WordGraph that is the output of the algorithm in a way that preserves it up to isomorphism.

Contents

`ToddCoxeter.perform_lookahead`(…)	Perform a lookahead.
`ToddCoxeter.perform_lookahead_for`(…)	Perform a lookahead for a specified amount of time.
`ToddCoxeter.perform_lookahead_until`(…)	Perform a lookahead until a nullary predicate returns `True`.
`ToddCoxeter.perform_lookbehind`(…)	Perform a lookbehind.
`ToddCoxeter.perform_lookbehind_no_checks`(…)	Perform a lookbehind using a function to decide whether or not to collapse nodes.
`ToddCoxeter.perform_lookbehind_for`(…)	Perform a lookbehind for a specified amount of time.
`ToddCoxeter.perform_lookbehind_for_no_checks`(…)	Perform a lookbehind for a specified amount of time with a collapser.
`ToddCoxeter.perform_lookbehind_until`(…)	Perform a lookbehind until a nullary predicate returns `True`.
`ToddCoxeter.perform_lookbehind_until_no_checks`(…)	Perform a lookbehind until a nullary predicate returns `True`.
`ToddCoxeter.shrink_to_fit`(…)	Shrink the underlying word graph to remove all dead nodes.
`ToddCoxeter.standardize`(…)	Standardize `ToddCoxeter.current_word_graph`.

Full API

ToddCoxeter.perform_lookahead(self: ToddCoxeter) → ToddCoxeter

Perform a lookahead.

This function can be used to explicitly perform a lookahead. The style and extent of this lookahead are controlled by the settings ToddCoxeter.lookahead_style and ToddCoxeter.lookahead_extent.

Returns:: self
Return type:: ToddCoxeter

ToddCoxeter.perform_lookahead_for(self: ToddCoxeter, t: datetime.timedelta) → ToddCoxeter

Perform a lookahead for a specified amount of time.

This function runs a lookahead for approximately the amount of time indicated by t, or until the lookahead is complete whichever happens first.

Parameters:: t (datetime.timedelta) – the time to run for.
Returns:: self
Return type:: ToddCoxeter

ToddCoxeter.perform_lookahead_until(self: ToddCoxeter, pred: collections.abc.Callable[[], bool]) → ToddCoxeter

Perform a lookahead until a nullary predicate returns True.

This function runs a lookahead until the nullary predicate pred returns True, or until the lookahead is complete whichever happens first.

Parameters:: pred (collections.abc.Callable[[], bool]) – the nullary predicate.
Returns:: self
Return type:: ToddCoxeter

ToddCoxeter.perform_lookbehind(self: ToddCoxeter) → ToddCoxeter

Perform a lookbehind.

This function performs a “lookbehind” 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.run_until(lambda: tc.number_of_nodes_active() >= 12_000_000)
tc.perform_lookahead();
tc.perform_lookbehind();

tc.number_of_classes() # returns 1

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

Returns:: self
Return type:: ToddCoxeter
Raises:: LibsemigroupsError – if self is a one-sided congruence and has any generating pairs (because in this case this function does nothing but still might take some time to run).

ToddCoxeter.perform_lookbehind_no_checks(self: ToddCoxeter, collapser: collections.abc.Callable[[Word], Word]) → ToddCoxeter

Perform a lookbehind using a function to decide whether or not to collapse nodes.

This function perform a lookbehind using the function collapser to decide whether or not to collapse nodes. For example, it might be the case that collapser uses a KnuthBendix instance to determine whether or not nodes in the graph represent the same class of the congruence. More specifically, the shortlex least path from the initial node to every node n is rewritten using collapser, and if the rewritten word labels a path in the graph to a node m, then it is assumed that m and n represent the same class of the congruence, and they are marked for collapsing. For example, perform_lookbehind calls perform_lookbehind_no_checks where collapser is the member function ToddCoxeter.reduce_no_run.

Parameters:: collapser (collections.abc.Callable[[Word], Word])) – a function taking a str or list[int] (depending on the type used by self for words) and which returns a word equivalent to the input word in the congruence represented by self.
Returns:: self
Return type:: ToddCoxeter
Raises:: LibsemigroupsError – if self is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run).

>>> from libsemigroups_pybind11 import (presentation, Presentation,
... ToddCoxeter, congruence_kind)
>>> from datetime import timedelta
>>> p = Presentation("abcdef")
>>> p.contains_empty_word(True)
<monoid presentation with 6 letters, 0 rules, and length 0>
>>> 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)
>>> tc.run_for(timedelta(seconds=0.01))
>>> tc.perform_lookbehind_no_checks(lambda w: "") # just an example, not good!
<2-sided ToddCoxeter over <monoid presentation with 6 letters, 9 rules, and length 87> with 0 gen. pairs + 1 node>
>>> tc.number_of_classes()
1

ToddCoxeter.perform_lookbehind_for(self: ToddCoxeter, t: datetime.timedelta) → ToddCoxeter

Perform a lookbehind for a specified amount of time.

This function runs a lookbehind for approximately the amount of time indicated by t, or until the lookbehind is complete whichever happens first.

Parameters:: t (datetime.timedelta) – the time to run for.
Returns:: self
Return type:: ToddCoxeter
Raises:: LibsemigroupsError – if self is a one-sided congruence and has any generating pairs (because in this case this function does nothing but still might take some time to run).

ToddCoxeter.perform_lookbehind_for_no_checks(self: ToddCoxeter, t: datetime.timedelta, collapser: collections.abc.Callable[[Word], Word]) → ToddCoxeter

Perform a lookbehind for a specified amount of time with a collapser.

This function runs a lookbehind using collapser for approximately the amount of time indicated by t, or until the lookbehind is complete whichever happens first. See perform_lookbehind_no_checks for more details.

Parameters:

t (datetime.timedelta) – the time to run for.
collapser (collections.abc.Callable[[Word], Word])) – a function taking a str or list[int] (depending on the type used by self for words) and which returns a word equivalent to the input word in the congruence represented by self.

Returns:

A reference to *this.

Returns:

self

Return type:

ToddCoxeter

Raises:

LibsemigroupsError – if self is a one-sided congruence and has any generating pairs (because in this case this function does nothing but still might take some time to run).

ToddCoxeter.perform_lookbehind_until(self: ToddCoxeter, pred: collections.abc.Callable[[], bool]) → ToddCoxeter

Perform a lookbehind until a nullary predicate returns True.

This function runs a lookbehind until the nullary predicate pred returns True, or until the lookbehind is complete whichever happens first.

Parameters:: pred (collections.abc.Callable[[], bool]) – the nullary predicate.
Returns:: self
Return type:: ToddCoxeter
Raises:: LibsemigroupsError – if self is a one-sided congruence and has any generating pairs (because in this case this function does nothing but still might take some time to run).

ToddCoxeter.perform_lookbehind_until_no_checks(self: ToddCoxeter, pred: collections.abc.Callable[[], bool], collapser: collections.abc.Callable[[Word], Word]) → ToddCoxeter

Perform a lookbehind until a nullary predicate returns True.

This function runs a lookbehind using collapser until the nullary predicate pred returns True, or until the lookbehind is complete whichever happens first.

Parameters:

pred (collections.abc.Callable[[], bool]) – the nullary predicate.
collapser (collections.abc.Callable[[Word], Word])) – a function taking a str or list[int] (depending on the type used by self for words) and which returns a word equivalent to the input word in the congruence represented by self.

Returns:

self

Return type:

ToddCoxeter

Raises:

LibsemigroupsError – if self is a one-sided congruence and has any generating pairs (because in this case this function does nothing but still might take some time to run).

ToddCoxeter.shrink_to_fit(self: ToddCoxeter) → None: Shrink the underlying word graph to remove all dead nodes. This function triggers a full enumeration, and standardization, and removes from word_graph any dead nodes. If Runner.finished returns False, then this function does nothing.

ToddCoxeter.standardize(self: ToddCoxeter, val: Order) → bool

Standardize ToddCoxeter.current_word_graph.

This function standardizes the return value of current_word_graph, and does not trigger any enumeration. See standardization_order for a full description. The return value of this function indicates whether or not the current_word_graph was modified. In other words, if this function returns True, then the word graph was not previously standardized with respect to val, and was modified by calling this function if False is returned, then the word graph was previously standardized with respect to val (although this might not have been known), and was not modified by calling this function.

Parameters:: val (Order) – the order of the standardization.
Returns:: Whether or not the word graph was modified by the standardization.
Return type:: bool