KnuthBendix helpers

This page contains the documentation for various helper functions for manipulating KnuthBendix objects. All such functions are contained in the submodule libsemigroups_pybind11.knuth_bendix.

Contents

`by_overlap_length`(…)	Run the Knuth-Bendix algorithm by considering all overlaps of a given length.
`is_reduced`(…)	Check if the all rules are reduced with respect to each other.
`non_trivial_classes`(…)	Overloaded function.
`normal_forms`(…)	This function returns a range object (with the same methods as `Paths`) containing normal forms of the classes of the congruence represented by an instance of `KnuthBendix`.
`partition`(…)	Partition a list of words.
`redundant_rule`(…)	Return a redundant rule or `None`.

Full API

This page contains the documentation for various helper functions for manipulating KnuthBendix objects. All such functions are contained in the submodule knuth_bendix.

knuth_bendix.by_overlap_length(kb: KnuthBendix) → None

Run the Knuth-Bendix algorithm by considering all overlaps of a given length.

This function runs the Knuth-Bendix algorithm on the rewriting system represented by a KnuthBendix instance by considering all overlaps of a given length \(n\) (according to the KnuthBendix.options.overlap) before those overlaps of length \(n + 1\).

Parameters:: kb (KnuthBendix) – the KnuthBendix instance.

See also

KnuthBendix.overlap_policy

knuth_bendix.is_reduced(kb: KnuthBendix) → bool

Check if the all rules are reduced with respect to each other.

Parameters:: kb (KnuthBendix) – the KnuthBendix instance defining the rules that are to be checked for being reduced.
Returns:: True if for each pair \((A, B)\) and \((C, D)\) of rules stored within the KnuthBendix instance, \(C\) is neither a subword of \(A\) nor \(B\). Returns False otherwise.
Return type:: bool

knuth_bendix.non_trivial_classes(*args, **kwargs)

Overloaded function.

knuth_bendix.non_trivial_classes(kb: KnuthBendix, 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 KnuthBendix instance kb.

Parameters:

kb (KnuthBendix) – the KnuthBendix instance.
words (list[list[int] | str]) – the input list of words.

Returns:

The partition of the input list.

Return type:

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

knuth_bendix.non_trivial_classes(kb1: KnuthBendix, kb2: KnuthBendix) → list[list[list[int]] | list[str]]

Find the non-trivial classes of the quotient of one KnuthBendix instance in another.

This function returns the classes with size at least \(2\) in the normal forms of kb2 in kb1 (the greater congruence, with fewer classes). This function triggers a full enumeration of both kb2 and kb1.

Note that this function does not compute the normal forms of kb2 and try to compute the partition of these induced by kb1, before filtering out the classes of size \(1\). In particular, it is possible to compute the non-trivial classes of kb1 in kb2 if there are only finitely many finite such classes, regardless of whether or not kb2 or kb1 has infinitely many classes.

Parameters:

kb1 (KnuthBendix) – the instance to compute the partition.
kb2 (KnuthBendix) – the instance whose normal forms will be partitioned.

Returns:

The non-trivial classes of kb1 in kb2.

Return type:

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

Raises:

LibsemigroupsError – if kb1 has infinitely many classes and kb2 has finitely many classes (so that there is at least one infinite non-trivial class).
LibsemigroupsError – if the alphabets of the presentations of kb1 and kb2 are not equal.
LibsemigroupsError – if the KnuthBendix.gilman_graph of kb1 has fewer nodes than that of kb2.

Warning

Termination of the Knuth-Bendix algorithm is undecidable in general, and this function may never terminate.

>>> from libsemigroups_pybind11 import (knuth_bendix, presentation,
... Presentation, congruence_kind, KnuthBendix)
>>> p = Presentation("abc")
>>> p.rules = ["ab", "ba", "ac", "ca", "aa", "a", "ac", "a", "ca",
... "a", "bc", "cb", "bbb", "b", "bc", "b", "cb", "b"]
>>> kb1 = KnuthBendix(congruence_kind.twosided, p)
>>> presentation.add_rule(p, "a", "b")
>>> kb2 = KnuthBendix(congruence_kind.twosided, p)
>>> knuth_bendix.non_trivial_classes(kb1, kb2)
[['b', 'ab', 'bb', 'abb', 'a']]
>>> p = Presentation([0, 1, 2])
>>> p.rules = [[0, 1], [1, 0], [0, 2], [2, 0], [0, 0], [0], [0, 2], [0], [2, 0],
... [0], [1, 2], [2, 1], [1, 1, 1], [1], [1, 2], [1], [2, 1], [1]]
>>> kb1 = KnuthBendix(congruence_kind.twosided, p)
>>> presentation.add_rule(p, [0], [1])
>>> kb2 = KnuthBendix(congruence_kind.twosided, p)
>>> knuth_bendix.non_trivial_classes(kb1, kb2)
[[[1], [0, 1], [1, 1], [0, 1, 1], [0]]]

knuth_bendix.normal_forms(kb: KnuthBendix) → Range

This function returns a range object (with the same methods as Paths) containing normal forms of the classes of the congruence represented by an instance of KnuthBendix. The order of the classes, and the normal form that is returned, are controlled by the reduction order used to construct kb. This function triggers a full enumeration of kb.

Parameters:: kb (KnuthBendix) – the KnuthBendix instance.
Returns:: A range object.
Return type:: Range

Warning

Termination of the Knuth-Bendix algorithm is undecidable in general, and this function may never terminate.

>>> from libsemigroups_pybind11 import (KnuthBendix, Presentation,
... presentation, congruence_kind, knuth_bendix)
>>> p = Presentation("abc")
>>> presentation.add_rule(p, "aaaa", "a")
>>> presentation.add_rule(p, "bbbb", "b")
>>> presentation.add_rule(p, "cccc", "c")
>>> presentation.add_rule(p, "abab", "aaa")
>>> presentation.add_rule(p, "bcbc", "bbb")
>>> kb = KnuthBendix(congruence_kind.twosided, p)
>>> kb.number_of_classes()
+∞
>>> list(knuth_bendix.normal_forms(kb).min(1).max(3))
['a', 'b', 'c', 'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

knuth_bendix.partition(kb: KnuthBendix, 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 KnuthBendix instance kb. This function triggers a full enumeration of kb.

Parameters:

kb (KnuthBendix) – the KnuthBendix instance.
words (list[list[int] | str]) – the input list of words.

Returns:

The partitioned list of words.

Return type:

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

knuth_bendix.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 Knuth-Bendix algorithm on the rules of the presentation except for a given omitted rule. For every such omitted rule, Knuth-Bendix 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:

p (Presentation) – the presentation.
t (datetime.timedelta) – time to run Knuth-Bendix for every omitted rule.

Returns:

A redundant rule or None.

Return type:

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

Warning

The progress of the Knuth-Bendix algorithm may differ between different calls to this function even if the parameters are identical. As such this is non-deterministic, and may produce different results with the same input.

>>> from libsemigroups_pybind11 import (knuth_bendix, presentation,
... Presentation)
>>> from datetime import timedelta
>>> p = Presentation("ab")
>>> presentation.add_rule(p, "ab", "ba")
>>> presentation.add_rule(p, "bab", "abb")
>>> t = timedelta(seconds = 1)
>>> p.rules
['ab', 'ba', 'bab', 'abb']
>>> knuth_bendix.redundant_rule(p, t)
('bab', 'abb')