Todd-Coxeter

This class contains the main implementation of the Todd-Coxeter algorithm for computing left, right, and 2-sided congruences on semigroups and monoids.

This page contains a summary of the main methods of the class ToddCoxeter.

In this documentation we use the term "coset enumeration" to mean the execution of (any version of) the Todd-Coxeter algorithm.

See also

congruence_kind and tril.

>>> from libsemigroups_pybind11 import congruence_kind, ToddCoxeter
>>> tc = ToddCoxeter(congruence_kind.left)            # construct a left congruence
>>> tc.set_number_of_generators(2)                    # 2 generators
>>> tc.add_pair([0, 0], [0])                          # generator 0 squared is itself
>>> tc.add_pair([0], [1])                             # generator 0 equals 1
>>> tc.strategy(ToddCoxeter.strategy_options.felsch)  # set the strategy
<ToddCoxeter object with 2 generators and 2 pairs>
>>> tc.number_of_classes()                            # calculate number of classes
1
>>> tc.contains([0, 0, 0, 0], [0, 0])                 # check if 2 words are equal
True
>>> tc.word_to_class_index([0, 0, 0, 0])              # get the index of a class
0
>>> tc.standardize(ToddCoxeter.order.lex)             # standardize to lex order
True

>>> from libsemigroups_pybind11 import congruence_kind, ToddCoxeter
>>> tc = ToddCoxeter(congruence_kind.twosided)
>>> tc.set_number_of_generators(4)
>>> tc.add_pair([0, 0], [0])
>>> tc.add_pair([1, 0], [1])
>>> tc.add_pair([0, 1], [1])
>>> tc.add_pair([2, 0], [2])
>>> tc.add_pair([0, 2], [2])
>>> tc.add_pair([3, 0], [3])
>>> tc.add_pair([0, 3], [3])
>>> tc.add_pair([1, 1], [0])
>>> tc.add_pair([2, 3], [0])
>>> tc.add_pair([2, 2, 2], [0])
>>> tc.add_pair([1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2], [0])
>>> tc.add_pair([1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3,
... 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3], [0])
>>> tc.strategy(ToddCoxeter.strategy_options.hlt).standardize(False)
<ToddCoxeter object with 4 generators and 12 pairs>
>>> tc.lookahead(ToddCoxeter.lookahead_options.partial).save(False)
<ToddCoxeter object with 4 generators and 12 pairs>
>>> tc.number_of_classes()
10752
>>> tc.complete()
True
>>> tc.compatible()
True
>>> S = tc.quotient_froidure_pin()             # quotient semigroup
>>> S.size()
10752
>>> S.number_of_idempotents()
1
>>> tc.standardize(ToddCoxeter.order.recursive)
True
>>> it = tc.normal_forms()
>>> [next(it) for _ in range(10)]
[[0], [1], [2], [2, 1], [1, 2], [1, 2, 1], [2, 2], [2, 2, 1], [2, 1, 2], [2, 1, 2, 1]]
>>> tc.standardize(ToddCoxeter.order.lex)
True
>>> it = tc.normal_forms()
>>> [next(it) for _ in range(10)]
[[0], [0, 1], [0, 1, 2], [0, 1, 2, 1], [0, 1, 2, 1, 2], [0, 1, 2, 1, 2, 1], [0, 1, 2, 1, 2, 1, 2], [0, 1, 2, 1, 2, 1, 2, 1], [0, 1, 2, 1, 2, 1, 2, 1, 2], [0, 1, 2, 1, 2, 1, 2, 1, 2, 1]]

ToddCoxeter(*args, **kwargs)

Overloaded function.

ToddCoxeter.add_pair(self, u, v)

Add a generating pair to the congruence.

ToddCoxeter.class_index_to_word(self, i)

If the congruence is defined over a semigroup with generators \(A\), then this function defines a injective function from \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes, to a fixed set of words over \(A\) representing distinct congruences classes.

ToddCoxeter.compatible(self)

Returns True if the coset table is compatible with the relations and generating pairs used to create this, and False if it is not.

ToddCoxeter.complete(self)

Returns True if the coset table is complete, and False if it is not.

ToddCoxeter.const_contains(self, u, v)

Check if a pair of words is known to belong to the congruence.

ToddCoxeter.contains(self, u, v)

Check if a pair of words belongs to the congruence.

ToddCoxeter.dead(self)

Check if the runner is dead.

ToddCoxeter.empty(self)

Returns True if there are no relations or generating pairs in the ToddCoxeter instance, and the number of active cosets is 1 (the minimum possible).

ToddCoxeter.finished(self)

Check if the main algorithm, implemented in this class, has been run to completion or not.

ToddCoxeter.froidure_pin_options(self, value)

Values for specifying whether to use relations or Cayley graph.

ToddCoxeter.froidure_pin_policy(*args, **kwargs)

Overloaded function.

ToddCoxeter.generating_pairs(self)

Returns an iterator pointing to the first generating pair of the congruence (if any).

ToddCoxeter.has_parent_froidure_pin(self)

Returns True if the congruence was created from a FroidurePin instance.

ToddCoxeter.has_quotient_froidure_pin(self)

Returns True if the congruence knows an isomorphic quotient semigroup represented by an instance of FroidurePin.

ToddCoxeter.is_quotient_obviously_finite(self)

Return True if the number of classes in the congruence is obviously finite, and False if it is not obviously finite.

ToddCoxeter.is_quotient_obviously_infinite(self)

Return True if the number of classes in the congruence is obviously infinite, and False if it is not obviously infinite.

ToddCoxeter.is_standardized(self)

Returns True if the ToddCoxeter instance is standardized.

ToddCoxeter.kill(self)

Stop running the main algorithm(s) (thread-safe).

ToddCoxeter.kind(self)

Return if the congruence was created as a left, right, or two-sided congruence.

ToddCoxeter.less(self, u, v)

This function returns True if the congruence class of v is less than the class of v in a total ordering of congruence classes.

ToddCoxeter.lookahead(self, arg0)

Sets the type of lookahead to be used when using the HLT strategy.

ToddCoxeter.lookahead_options(self, value)

Values for specifying the type of lookahead to perform.

ToddCoxeter.lower_bound(self, arg0)

Sets a lower bound for the number of classes of the congruence represented by a ToddCoxeter instance.

ToddCoxeter.next_lookahead(self, arg0)

If the number of cosets active exceeds the value set by this function, then a lookahead, of the type set by lookahead, is triggered.

ToddCoxeter.non_trivial_classes(self)

Returns the words belonging to non-trivial class with given index.

ToddCoxeter.normal_forms(self)

Returns an iterator to the normal forms of the congruence represented by an instance of ToddCoxeter.

ToddCoxeter.number_of_classes(self)

Returns the number of classes in the congruence.

ToddCoxeter.number_of_generating_pairs(self)

Returns the number of generating pairs added by add_pair().

ToddCoxeter.number_of_generators(self)

Returns the number of generators specified by set_number_of_generators().

ToddCoxeter.number_of_non_trivial_classes(self)

Returns the number of non-trivial classes (size > 1) of the congruence.

ToddCoxeter.order(self, value)

The possible arguments for standardize().

ToddCoxeter.parent_froidure_pin(self)

Returns the FroidurePin over which the congruence was defined, if it exists.

ToddCoxeter.quotient_froidure_pin(self)

Returns a semigroup represented as FroidurePin that is isomorphic to the quotient of the parent semigroup by the 2-sided congruence that this represents.

ToddCoxeter.random_interval(self, arg0)

Sets the duration in nanoseconds that a given randomly selected strategy will run for, when using the random strategy (ToddCoxeter.strategy_options.random).

ToddCoxeter.random_shuffle_generating_pairs(self)

Randomly shuffle all existing generating pairs.

ToddCoxeter.report(self)

Check if it is time to report.

ToddCoxeter.report_every(self, t)

Set the minimum elapsed time between reports.

ToddCoxeter.report_why_we_stopped(self)

Report why we stopped.

ToddCoxeter.reserve(self, arg0)

Reserves the capacity specified by the argument in the data structures for cosets used in a ToddCoxeter instance.

ToddCoxeter.run(self)

Run the algorithm until it finishes.

ToddCoxeter.run_for(self, t)

Run for a specified amount of time.

ToddCoxeter.run_until(self, func)

Run until a nullary predicate returns True or finished().

ToddCoxeter.save(self, arg0)

If the argument of this function is True and the HLT strategy is being used, then deductions are processed during the enumeration.

ToddCoxeter.set_number_of_generators(self, n)

Set the number of generators of the congruence.

ToddCoxeter.shrink_to_fit(self)

Release all memory used to store free cosets, and any other unnecessary data if the enumeration is finished.

ToddCoxeter.sort_generating_pairs(self, func)

Sorts all existing generating pairs according to the binary function func.

ToddCoxeter.standardize(*args, **kwargs)

Overloaded function.

ToddCoxeter.stopped_by_predicate(self)

Check if the main algorithm was, or should be, stopped by the nullary predicate passed as first argument to run_until().

ToddCoxeter.strategy(*args, **kwargs)

Overloaded function.

ToddCoxeter.strategy_options(self, value)

Values for defining the strategy.

ToddCoxeter.timed_out(self)

Check if the main algorithm has or should timed out.

ToddCoxeter.word_to_class_index(self, w)

If the congruence, that an object of this type represents, is defined over a semigroup with generators \(A\), then this function defines a surjective function from the set of all words over \(A\) to either \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes.

ToddCoxeter.to_gap_string(self)

Returns a string containing a GAP definition of the finitely presented semigroup represented by a ToddCoxeter instance.
class ToddCoxeter(*args, **kwargs)

Overloaded function.

  1. __init__(self: _libsemigroups_pybind11.ToddCoxeter, kind: _libsemigroups_pybind11.congruence_kind) -> None

    Construct from kind (left/right/2-sided) and options.

    Constructs an empty instance of an interface to a congruence of type specified by the argument.

    Parameters

    • kind (congruence_kind) the handedness of the congruence.

    Complexity

    Constant.

    See also

    set_number_of_generators() and add_pair().

  2. __init__(self: _libsemigroups_pybind11.ToddCoxeter, knd: _libsemigroups_pybind11.congruence_kind, tc: _libsemigroups_pybind11.ToddCoxeter) -> None

    Construct from kind (left/right/2-sided) and ToddCoxeter.

    This constructor creates a new ToddCoxeter instance representing a left, right, or two-sided congruence over the quotient semigroup represented by a ToddCoxeter instance.

    Parameters

    • knd (congruence_kind) the handedness of the congruence.

    • tc (ToddCoxeter) the ToddCoxeter representing the underlying semigroup

    Raises

    RuntimeError - if tc is a left, or right, congruence, and knd is not left, or not right, respectively.

  3. __init__(self: _libsemigroups_pybind11.ToddCoxeter, knd: _libsemigroups_pybind11.congruence_kind, kb: _libsemigroups_pybind11.KnuthBendix) -> None

    Construct from kind (left/right/2-sided) and KnuthBendix.

    A constructor that creates a new ToddCoxeter instance representing a left, right, or two-sided congruence over the semigroup represented by a KnuthBendix instance.

    Parameters

    • knd (congruence_kind) the handedness of the congruence.

    • kb (KnuthBendix) the KnuthBendix representing the underlying semigroup.

  4. __init__(self: _libsemigroups_pybind11.ToddCoxeter, arg0: _libsemigroups_pybind11.ToddCoxeter) -> None

    Copy constructor.

    Constructs a complete copy of that, including all of the settings, table, defining relations, and generating pairs.

    Parameters

    • that (ToddCoxeter) the ToddCoxeter instance to copy.

  5. __init__(self: _libsemigroups_pybind11.ToddCoxeter, arg0: _libsemigroups_pybind11.congruence_kind, arg1: libsemigroups::FroidurePinBase) -> None

    Construct from kind (left/right/2-sided) and FroidurePin.

    This constructor creates a ToddCoxeter instance representing a left, right, or two-sided congruence over the semigroup represented by a FroidurePin object.

    Parameters

    • knd (congruence_kind) the kind of the congruence being constructed

    • fp (FroidurePin) the semigroup over which the congruence is to be defined.

add_pair(self: _libsemigroups_pybind11.ToddCoxeter, u: List[int], v: List[int]) → None

Add a generating pair to the congruence.

Parameters

  • u (List[int]) -- a word over the generators of the semigroup.

  • v (List[int]) -- a word over the generators of the semigroup.

Returns

(None)

class_index_to_word(self: _libsemigroups_pybind11.ToddCoxeter, i: int) → List[int]

If the congruence is defined over a semigroup with generators \(A\), then this function defines a injective function from \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes, to a fixed set of words over \(A\) representing distinct congruences classes.

Parameters

i (int) -- the index of the class whose representative we want to find

Returns

The word representing the i-th class of the congruence

compatible(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Returns True if the coset table is compatible with the relations and generating pairs used to create this, and False if it is not.

complete(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Returns True if the coset table is complete, and False if it is not.

const_contains(self: _libsemigroups_pybind11.ToddCoxeter, u: List[int], v: List[int]) → _libsemigroups_pybind11.tril

Check if a pair of words is known to belong to the congruence.

Parameters

  • u (List[int]) -- a word over the generators of the semigroup.

  • v (List[int]) -- a word over the generators of the semigroup.

Returns

tril.TRUE if the words u and v are known to belong to the same congruence class tril.FALSE if the words are known to not belong to the same congruence class tril.unknown otherwise.

contains(self: _libsemigroups_pybind11.ToddCoxeter, u: List[int], v: List[int]) → bool

Check if a pair of words belongs to the congruence.

Parameters

  • u (List[int]) -- a word over the generators of the semigroup.

  • v (List[int]) -- a word over the generators of the semigroup.

Returns

True if the words u and v belong to the same congruence class, and False otherwise.

dead(self: libsemigroups::Runner) → bool

Check if the runner is dead.

Parameters

None

Returns

A bool.

empty(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Returns True if there are no relations or generating pairs in the ToddCoxeter instance, and the number of active cosets is 1 (the minimum possible).

finished(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Check if the main algorithm, implemented in this class, has been run to completion or not.

Parameters

None

Returns

A bool.

class froidure_pin_options(self: _libsemigroups_pybind11.ToddCoxeter.froidure_pin_options, value: int)

Values for specifying whether to use relations or Cayley graph.

The values in this enum can be used as the argument for froidure_pin_policy() to specify whether the defining relations, or the left/right Cayley graph, of a FroidurePin instance, should be used in the coset enumeration.

If the number of classes in the congruence represented by a ToddCoxeter instance is relatively small, by some definition, compared to the size of the semigroup represented by the FroidurePin instance, then the use_relations option is often faster. If the number of classes is relatively large, then use_cayley_graph is often faster.

It is guaranteed that run will terminate in an amount of time proportionate to the size of the input if the policy use_cayley_graph is used, whereas the run time when using the policy use_relations can be arbitrarily high regardless of the size of the input.

Members:

none :

No policy has been specified.

use_relations :

Use the relations of a FroidurePin instance.

use_cayley_graph :

Use the left or right Cayley graph of a FroidurePin instance.

property name
froidure_pin_policy(*args, **kwargs)

Overloaded function.

  1. froidure_pin_policy(self: _libsemigroups_pybind11.ToddCoxeter, arg0: _libsemigroups_pybind11.ToddCoxeter.froidure_pin_options) -> _libsemigroups_pybind11.ToddCoxeter

    Sets the value of the Froidure-Pin policy specified by the argument ToddCoxeter.froidure_pin_options.

  2. froidure_pin_policy(self: _libsemigroups_pybind11.ToddCoxeter) -> _libsemigroups_pybind11.ToddCoxeter.froidure_pin_options

    Gets the value of the Froidure-Pin policy.

generating_pairs(self: _libsemigroups_pybind11.ToddCoxeter) → Iterator

Returns an iterator pointing to the first generating pair of the congruence (if any).

Parameters

None

Returns

An iterator.

has_parent_froidure_pin(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Returns True if the congruence was created from a FroidurePin instance.

Parameters

None

Returns

A bool.

has_quotient_froidure_pin(self: libsemigroups::CongruenceInterface) → bool

Returns True if the congruence knows an isomorphic quotient semigroup represented by an instance of FroidurePin.

Parameters

None

Returns

A bool.

is_quotient_obviously_finite(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Return True if the number of classes in the congruence is obviously finite, and False if it is not obviously finite.

Parameters

None

Returns

A bool.

is_quotient_obviously_infinite(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Return True if the number of classes in the congruence is obviously infinite, and False if it is not obviously infinite.

Parameters

None

Returns

A bool.

is_standardized(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Returns True if the ToddCoxeter instance is standardized.

kill(self: libsemigroups::Runner) → None

Stop running the main algorithm(s) (thread-safe).

Parameters

None

Returns

(None).

kind(self: _libsemigroups_pybind11.ToddCoxeter) → _libsemigroups_pybind11.congruence_kind

Return if the congruence was created as a left, right, or two-sided congruence.

Parameters

None

Returns

A congruence_kind.

less(self: _libsemigroups_pybind11.ToddCoxeter, u: List[int], v: List[int]) → bool

This function returns True if the congruence class of v is less than the class of v in a total ordering of congruence classes.

Parameters

  • u (List[int]) -- a word over the generators of the semigroup.

  • v (List[int]) -- a word over the generators of the semigroup.

Returns

True if the class of u is less than that of v.

lookahead(self: _libsemigroups_pybind11.ToddCoxeter, arg0: _libsemigroups_pybind11.ToddCoxeter.lookahead_options) → _libsemigroups_pybind11.ToddCoxeter

Sets the type of lookahead to be used when using the HLT strategy.

class lookahead_options(self: _libsemigroups_pybind11.ToddCoxeter.lookahead_options, value: int)

Values for specifying the type of lookahead to perform.

The values in this enum can be used as the argument for lookahead() to specify the type of lookahead that should be performed when using the HLT strategy.

Members:

full :

A full lookahead is one starting from the initial coset. Full lookaheads are therefore sometimes slower but may detect more coincidences than a partial lookahead.

partial :

A partial lookahead is one starting from the current coset. Partial lookaheads are therefore sometimes faster but may not detect as many coincidences as a full lookahead.

property name
lower_bound(self: _libsemigroups_pybind11.ToddCoxeter, arg0: int) → _libsemigroups_pybind11.ToddCoxeter

Sets a lower bound for the number of classes of the congruence represented by a ToddCoxeter instance.

next_lookahead(self: _libsemigroups_pybind11.ToddCoxeter, arg0: int) → _libsemigroups_pybind11.ToddCoxeter

If the number of cosets active exceeds the value set by this function, then a lookahead, of the type set by lookahead, is triggered.

non_trivial_classes(self: _libsemigroups_pybind11.ToddCoxeter) → Iterator

Returns the words belonging to non-trivial class with given index.

Parameters

i (int) -- the index of the non-trivial class.

Returns

A List[List[int]].

normal_forms(self: _libsemigroups_pybind11.ToddCoxeter) → Iterator

Returns an iterator to the normal forms of the congruence represented by an instance of ToddCoxeter.

number_of_classes(self: _libsemigroups_pybind11.ToddCoxeter) → int

Returns the number of classes in the congruence.

Parameters

None

Returns

The number of congruences classes of this if this number is finite, or POSITIVE_INFINITY in some cases if this number is not finite.

number_of_generating_pairs(self: _libsemigroups_pybind11.ToddCoxeter) → int

Returns the number of generating pairs added by add_pair().

Returns

The number of generating pairs of the congruence that an object of this type represents.

number_of_generators(self: _libsemigroups_pybind11.ToddCoxeter) → int

Returns the number of generators specified by set_number_of_generators().

Parameters

None

Returns

The number of generators of the semigroup of the congruence, or UNDEFINED.

number_of_non_trivial_classes(self: _libsemigroups_pybind11.ToddCoxeter) → int

Returns the number of non-trivial classes (size > 1) of the congruence.

Parameters

None

Returns

The number of non-trivial classes of the congruence.

class order(self: _libsemigroups_pybind11.ToddCoxeter.order, value: int)

The possible arguments for standardize().

The values in this enum can be used as the argument for standardize() to specify which ordering should be used. The normal forms for congruence classes are given with respect to one of the orders specified by the values in this enum.

Members:

none :

No standardization has been done.

shortlex :

Normal forms are the short-lex least word belonging to a given congruence class.

lex :

Normal forms are the lexicographical least word belonging to a given congruence class.

recursive :

Normal forms are the recursive-path least word belonging to a given congruence class.

property name
parent_froidure_pin(self: _libsemigroups_pybind11.ToddCoxeter) → libsemigroups::FroidurePinBase

Returns the FroidurePin over which the congruence was defined, if it exists.

Parameters

None

Returns

A FroidurePin.

quotient_froidure_pin(self: _libsemigroups_pybind11.ToddCoxeter) → libsemigroups::FroidurePinBase

Returns a semigroup represented as FroidurePin that is isomorphic to the quotient of the parent semigroup by the 2-sided congruence that this represents.

Parameters

None

Returns

A FroidurePin.

random_interval(self: _libsemigroups_pybind11.ToddCoxeter, arg0: datetime.timedelta) → _libsemigroups_pybind11.ToddCoxeter

Sets the duration in nanoseconds that a given randomly selected strategy will run for, when using the random strategy (ToddCoxeter.strategy_options.random).

random_shuffle_generating_pairs(self: _libsemigroups_pybind11.ToddCoxeter) → _libsemigroups_pybind11.ToddCoxeter

Randomly shuffle all existing generating pairs.

report(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Check if it is time to report.

Parameters

None

Returns

A bool.

report_every(self: _libsemigroups_pybind11.ToddCoxeter, t: datetime.timedelta) → None

Set the minimum elapsed time between reports.

Parameters

t (datetime.timedelta) -- the amount of time between reports.

Returns

(None)

report_why_we_stopped(self: _libsemigroups_pybind11.ToddCoxeter) → None

Report why we stopped.

Parameters

None

Returns

(None)

reserve(self: _libsemigroups_pybind11.ToddCoxeter, arg0: int) → None

Reserves the capacity specified by the argument in the data structures for cosets used in a ToddCoxeter instance.

run(self: _libsemigroups_pybind11.ToddCoxeter) → None

Run the algorithm until it finishes. :Parameters: None

Returns

(None)

run_for(self: _libsemigroups_pybind11.ToddCoxeter, t: datetime.timedelta) → None

Run for a specified amount of time.

Parameters

t (datetime.timedelta) -- the time to run for.

Returns

(None)

>>> from datetime import timedelta
>>> from libsemigroups_pybind11 import ToddCoxeter, congruence_kind
>>> tc = ToddCoxeter(congruence_kind.twosided)
>>> tc.set_number_of_generators(1)
>>> tc.add_pair([0] * 1000, [0] * 999)
>>> tc.run_for(timedelta(microseconds=10))
run_until(self: _libsemigroups_pybind11.ToddCoxeter, func: Callable[[], bool]) → None

Run until a nullary predicate returns True or finished().

Parameters

func (Callable[], bool) -- a function.

Returns

(None)

save(self: _libsemigroups_pybind11.ToddCoxeter, arg0: bool) → _libsemigroups_pybind11.ToddCoxeter

If the argument of this function is True and the HLT strategy is being used, then deductions are processed during the enumeration.

set_number_of_generators(self: _libsemigroups_pybind11.ToddCoxeter, n: int) → None

Set the number of generators of the congruence.

Parameters

n (int) -- the number of generators.

Returns

(None)

shrink_to_fit(self: _libsemigroups_pybind11.ToddCoxeter) → None

Release all memory used to store free cosets, and any other unnecessary data if the enumeration is finished.

sort_generating_pairs(self: _libsemigroups_pybind11.ToddCoxeter, func: Callable[[List[int], List[int]], bool]) → _libsemigroups_pybind11.ToddCoxeter

Sorts all existing generating pairs according to the binary function func.

Parameters

func (Callable[], bool) -- a binary predicate that defines a linear order on the relations in a ToddCoxeter instance.

standardize(*args, **kwargs)

Overloaded function.

  1. standardize(self: _libsemigroups_pybind11.ToddCoxeter, arg0: bool) -> _libsemigroups_pybind11.ToddCoxeter

    If the argument of this function is True, then the coset table is standardized (according to the short-lex order) during the coset enumeration.

  2. standardize(self: _libsemigroups_pybind11.ToddCoxeter, arg0: _libsemigroups_pybind11.ToddCoxeter.order) -> bool

    If the argument of this function is True, then the coset table is standardized (according to the short-lex order) during the coset enumeration.

stopped_by_predicate(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Check if the main algorithm was, or should be, stopped by the nullary predicate passed as first argument to run_until().

Parameters

None

Returns

A bool.

strategy(*args, **kwargs)

Overloaded function.

  1. strategy(self: _libsemigroups_pybind11.ToddCoxeter) -> _libsemigroups_pybind11.ToddCoxeter.strategy_options

    Returns the value of the strategy used during the coset enumeration.

  2. strategy(self: _libsemigroups_pybind11.ToddCoxeter, arg0: _libsemigroups_pybind11.ToddCoxeter.strategy_options) -> _libsemigroups_pybind11.ToddCoxeter

    Set the strategy used during the coset enumeration can be specified using this function.

class strategy_options(self: _libsemigroups_pybind11.ToddCoxeter.strategy_options, value: int)

Values for defining the strategy.

The values in this enum can be used as the argument for the method strategy() to specify which strategy should be used when performing a coset enumeration.

Members:

hlt :

This value indicates that the HLT (Hazelgrove-Leech-Trotter) strategy should be used. This is analogous to ACE's R-style.

felsch :

This value indicates that the Felsch strategy should be used. This is analogous to ACE's C-style.

random :

This value indicates that a random combination of the HLT and Felsch strategies should be used. A random strategy (and associated options) are selected from one of the 10 options:

  1. HLT + full lookahead + no deduction processing + standardization

  2. HLT + full lookahead + deduction processing + standardization

  3. HLT + full lookahead + no deduction processing + no standardization

  4. HLT + full lookahead + deduction processing + no standardization

  5. HLT + partial lookahead + no deduction processing + standardization

  6. HLT + partial lookahead + deduction processing + standardization

  7. HLT + partial lookahead + no deduction processing + no standardization

  8. HLT + partial lookahead + deduction processing + no standardization

  9. Felsch + standardization

  10. Felsch + no standardization

and this strategy is then run for approximately the amount of time specified by the setting random_interval().

property name
timed_out(self: _libsemigroups_pybind11.ToddCoxeter) → bool

Check if the main algorithm has or should timed out.

Parameters

None

Returns

A bool.

to_gap_string(self: _libsemigroups_pybind11.ToddCoxeter) → str

Returns a string containing a GAP definition of the finitely presented semigroup represented by a ToddCoxeter instance.

Parameters

None

Returns

A string

word_to_class_index(self: _libsemigroups_pybind11.ToddCoxeter, w: List[int]) → int

If the congruence, that an object of this type represents, is defined over a semigroup with generators \(A\), then this function defines a surjective function from the set of all words over \(A\) to either \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes.

Parameters

w (List[int]) -- the word whose class index we want to find.

Returns

The index of the congruence class corresponding to the word.