Knuth-Bendix¶

On this page we describe the functionality relating to the Knuth-Bendix algorithm for semigroups and monoids that is available in libsemigroups_pybind11. This page contains a details of the methods of the class KnuthBendix. This class is used to represent a string rewriting system defining a finitely presented monoid or semigroup.

>>> from libsemigroups_pybind11 import KnuthBendix
>>> kb = KnuthBendix()
>>> kb.set_alphabet("abc")
>>> kb.add_rule("aaaa", "a")
>>> kb.add_rule("bbbb", "b")
>>> kb.add_rule("cccc", "c")
>>> kb.add_rule("abab", "aaa")
>>> kb.add_rule("bcbc", "bbb")
>>> not kb.confluent()
True
>>> kb.run()
>>> kb.number_of_active_rules()
31
>>> kb.confluent()
True

`KnuthBendix`	Default constructor.
`KnuthBendix.active_rules`	Returns a copy of the active rules of the KnuthBendix instance.
`KnuthBendix.add_rule`	Overloaded function.
`KnuthBendix.add_rules`	Overloaded function.
`KnuthBendix.alphabet`	Overloaded function.
`KnuthBendix.char_to_uint`	Convert a single letter `string` to a `int` representing the same generator.
`KnuthBendix.check_confluence_interval`	Set the interval at which confluence is checked.
`KnuthBendix.confluent`	Check if the KnuthBendix instance is confluent.
`KnuthBendix.contains_empty_string`	Returns whether or not the empty string belongs to the finitely presented semigroup represented by this.
`KnuthBendix.dead`	Check if the runner is dead.
`KnuthBendix.equal_to`	Overloaded function.
`KnuthBendix.finished`	Check if the main algorithm, implemented in this class, has been run to completion or not.
`KnuthBendix.froidure_pin`	Returns a `FroidurePin` instance isomorphic to the finitely presented semigroup defined by this.
`KnuthBendix.gilman_digraph`	Returns the associated Gilman digraph (or automata).
`KnuthBendix.has_froidure_pin`	Returns `True` if a `FroidurePin` instance isomorphic to the finitely presented semigroup defined by this has already been computed, and `False` if not.
`KnuthBendix.identity`	Returns the identity of this, or raises an exception if there isn't one.
`KnuthBendix.inverses`	Returns the inverses of this, or raises an exception if there aren't any.
`KnuthBendix.is_obviously_finite`	Return `True` if the finitely presented semigroup represented by this is obviously finite, and `False` if it is not obviously finite.
`KnuthBendix.is_obviously_infinite`	Returns `True` if the finitely presented semigroup represented by this is obviously infinite, and `False` if it is not obviously infinite.
`KnuthBendix.kill`	Stop running the main algorithm(s) (thread-safe).
`KnuthBendix.knuth_bendix_by_overlap_length`	Run the Knuth-Bendix algorithm by overlap length.
`KnuthBendix.max_overlap`	Set the maximum length of overlaps to be considered.
`KnuthBendix.max_rules`	Set the maximum number of rules.
`KnuthBendix.normal_form`	Overloaded function.
`KnuthBendix.normal_forms`	Returns an iterator to the normal forms with length in the given range.
`KnuthBendix.normal_forms_alphabet`	Returns an iterator to the normal forms of the congruence using the specified alphabet, and with length in the given range.
`KnuthBendix.number_of_active_rules`	Returns the current number of active rules in the KnuthBendix instance.
`KnuthBendix.number_of_normal_forms`	Returns the number of normal forms with length in a given range.
`KnuthBendix.number_of_rules`	Returns the number of rules of the finitely presented semigroup.
`KnuthBendix.overlap`	Values for specifying how to measure the length of an overlap.
`KnuthBendix.overlap_policy`	Set the overlap policy.
`KnuthBendix.report`	Check if it is time to report.
`KnuthBendix.report_every`	Set the minimum elapsed time between reports.
`KnuthBendix.report_why_we_stopped`	Report why we stopped.
`KnuthBendix.rules`	Returns an iterator to the generating pairs of the congruence.
`KnuthBendix.running`	Check if currently running.
`KnuthBendix.run`	Run the algorithm until it finishes.
`KnuthBendix.run_for`	Run for a specified amount of time.
`KnuthBendix.run_until`	Run until a nullary predicate returns `True` or `finished()`.
`KnuthBendix.set_alphabet`	Overloaded function.
`KnuthBendix.set_identity`	Overloaded function.
`KnuthBendix.set_inverses`	Set the inverses of letters in alphabet().
`KnuthBendix.size`	Returns the size of the finitely presented semigroup.
`KnuthBendix.started`	Check if `run()` has been called at least once before.
`KnuthBendix.stopped_by_predicate`	Check if the main algorithm was, or should be, stopped by the nullary predicate passed as first argument to `run_until()`.
`KnuthBendix.string_to_word`	Convert a string to a list of `int` representing the same element of the finitely presented semigroup represented by this.
`KnuthBendix.timed_out`	Check if the main algorithm has or should timed out.
`KnuthBendix.to_gap_string`	Returns a string containing GAP commands for defining a finitely presented semigroup equal to that represented by this.
`KnuthBendix.uint_to_char`	Convert an `int` to a `char` representing the same generator of the finitely presented semigroup represented by this.
`KnuthBendix.validate_letter`	Overloaded function.
`KnuthBendix.validate_word`	Overloaded function.
`KnuthBendix.word_to_string`	Convert a list of `int` to a string representing the same element of the finitely presented semigroup represented by this.

class KnuthBendix(self: _libsemigroups_pybind11.KnuthBendix)¶

Default constructor.

active_rules(self: _libsemigroups_pybind11.KnuthBendix) → List[Tuple[str, str]]¶

Returns a copy of the active rules of the KnuthBendix instance.

Parameters: None
Returns: A copy of the currently active rules.

add_rule(*args, **kwargs)¶

Overloaded function.

add_rule(self: _libsemigroups_pybind11.KnuthBendix, u: str, v: str) -> None
Add a rule.
Parameters
u (str) - the left-hand side of the rule being added.

v (str) - the right-hand side of the rule being added.
Returns

None
add_rule(self: _libsemigroups_pybind11.KnuthBendix, u: List[int], v: List[int]) -> None
Add a rule.
Parameters
u (List[int]) - the left-hand side of the rule.

v (List[int]) - the right-hand side of the rule.
Returns

None
add_rule(self: _libsemigroups_pybind11.KnuthBendix, rel: Tuple[str, str]) -> None

Add a rule.

Parameters

rel (Tuple[str, str]) - the rule being added.

Returns

None

add_rules(*args, **kwargs)¶

Overloaded function.

add_rules(self: _libsemigroups_pybind11.KnuthBendix, rels: List[Tuple[str, str]]) -> None

Add the rules in a list.

Parameters

rels (List[Tuple[str, str]]) - list of rules to add.

Returns

None
add_rules(self: _libsemigroups_pybind11.KnuthBendix, rels: libsemigroups::FroidurePinBase) -> None

Add the rules in a FroidurePin instance.

Parameters

rels (FroidurePin) - the instance.

Returns

None

alphabet(*args, **kwargs)¶

Overloaded function.

alphabet(self: _libsemigroups_pybind11.KnuthBendix) -> str

Returns the alphabet.

Parameters

None

Returns

A string.
alphabet(self: _libsemigroups_pybind11.KnuthBendix, i: int) -> str

Returns the i-th letter of the alphabet of the finitely presented semigroup represented by this.

Parameters

i (int) - the index of the letter.

Returns

A string.

char_to_uint(self: _libsemigroups_pybind11.KnuthBendix, a: str) → int¶

Convert a single letter string to a int representing the same generator.

Parameters: a (str) -- the string to convert.
Returns: an int.

check_confluence_interval(self: _libsemigroups_pybind11.KnuthBendix, val: int) → _libsemigroups_pybind11.KnuthBendix¶

Set the interval at which confluence is checked.

Parameters: val (int) -- the new value of the interval.
Returns: self.

confluent(self: _libsemigroups_pybind11.KnuthBendix) → bool¶

Check if the KnuthBendix instance is confluent.

Parameters: None
Returns: True if the KnuthBendix instance is confluent and False if it is not.

contains_empty_string(self: _libsemigroups_pybind11.KnuthBendix) → bool¶

Returns whether or not the empty string belongs to the finitely presented semigroup represented by this.

Returns: A bool.

dead(self: libsemigroups::Runner) → bool¶

Check if the runner is dead.

Parameters: None
Returns: A bool.

equal_to(*args, **kwargs)¶

Overloaded function.

equal_to(self: _libsemigroups_pybind11.KnuthBendix, u: str, v: str) -> bool
Check if two words represent the same element.
Parameters
u (str) - first word for comparison.

v (str) - second word for comparison.
Returns

True if the strings u and v represent the same element of the finitely presented semigroup, and False otherwise.
equal_to(self: _libsemigroups_pybind11.KnuthBendix, u: List[int], v: List[int]) -> bool
Check if two words represent the same element.
Parameters
u (List[int]) - first word for comparison.

v (List[int]) - second word for comparison.
Returns

True if the words u and v represent the same element of the finitely presented semigroup, and False otherwise.

finished(self: _libsemigroups_pybind11.KnuthBendix) → bool¶

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

Parameters: None
Returns: A bool.

froidure_pin(self: _libsemigroups_pybind11.KnuthBendix) → libsemigroups::FroidurePinBase¶

Returns a FroidurePin instance isomorphic to the finitely presented semigroup defined by this.

Parameters: None
Returns: A FroidurePin.

gilman_digraph(self: _libsemigroups_pybind11.KnuthBendix) → _libsemigroups_pybind11.ActionDigraph¶

Returns the associated Gilman digraph (or automata).

Parameters: None
Returns: A copy of an ActionDigraph.

has_froidure_pin(self: _libsemigroups_pybind11.KnuthBendix) → bool¶

Returns True if a FroidurePin instance isomorphic to the finitely presented semigroup defined by this has already been computed, and False if not.

Parameters: None
Returns: A bool.

identity(self: _libsemigroups_pybind11.KnuthBendix) → str¶

Returns the identity of this, or raises an exception if there isn't one.

Parameters: None
Returns: A string of length 1.

inverses(self: _libsemigroups_pybind11.KnuthBendix) → str¶

Returns the inverses of this, or raises an exception if there aren't any.

Parameters: None
Returns: A str.

is_obviously_finite(self: _libsemigroups_pybind11.KnuthBendix) → bool¶

Return True if the finitely presented semigroup represented by this is obviously finite, and False if it is not obviously finite.

Returns: A bool.

is_obviously_infinite(self: _libsemigroups_pybind11.KnuthBendix) → bool¶

Returns True if the finitely presented semigroup represented by this is obviously infinite, and False if it is not obviously infinite.

Returns: A bool.

kill(self: libsemigroups::Runner) → None¶

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

Parameters: None
Returns: (None).

knuth_bendix_by_overlap_length(self: _libsemigroups_pybind11.KnuthBendix) → None¶

Run the Knuth-Bendix algorithm by overlap length.

Parameters: None
Returns: None

max_overlap(self: _libsemigroups_pybind11.KnuthBendix, val: int) → _libsemigroups_pybind11.KnuthBendix¶

Set the maximum length of overlaps to be considered.

Parameters: val (int) -- the new value of the maximum overlap length.
Returns: self.

max_rules(self: _libsemigroups_pybind11.KnuthBendix, val: int) → _libsemigroups_pybind11.KnuthBendix¶

Set the maximum number of rules.

Parameters: val (int) -- the maximum number of rules.
Returns: self.

normal_form(*args, **kwargs)¶

Overloaded function.

normal_form(self: _libsemigroups_pybind11.KnuthBendix, w: str) -> str

Returns a normal form for a string.

Parameters

w (str) - the word whose normal form we want to find.

Returns

A str.
normal_form(self: _libsemigroups_pybind11.KnuthBendix, w: List[int]) -> List[int]

Returns a normal form for a word.

Parameters

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

Returns

The normal form of the parameter w.

normal_forms(self: _libsemigroups_pybind11.KnuthBendix, mn: int, mx: int) → Iterator¶

Returns an iterator to the normal forms with length in the given range.

Parameters

mn (int) -- the minimum length.
mx (int) -- the maximum length.

Returns

An iterator.

normal_forms_alphabet(self: _libsemigroups_pybind11.KnuthBendix, lphbt: str, mn: int, mx: int) → Iterator¶

Returns an iterator to the normal forms of the congruence using the specified alphabet, and with length in the given range.

Parameters

lphbt (str) -- the alphabet.
mn (int) -- the minimum length.
mx (int) -- the maximum length.

Returns

An iterator.

number_of_active_rules(self: _libsemigroups_pybind11.KnuthBendix) → int¶

Returns the current number of active rules in the KnuthBendix instance.

Parameters: None
Returns: An int.

number_of_normal_forms(self: _libsemigroups_pybind11.KnuthBendix, min: int, max: int) → int¶

Returns the number of normal forms with length in a given range.

Parameters

min (int) -- the minimum length of a normal form to count
max (int) -- one larger than the maximum length of a normal form to count.

Returns

An int.

number_of_rules(self: _libsemigroups_pybind11.KnuthBendix) → int¶

Returns the number of rules of the finitely presented semigroup.

Parameters: None
Returns: A int.

class overlap(self: _libsemigroups_pybind11.KnuthBendix.overlap, value: int)¶

Values for specifying how to measure the length of an overlap.

The values in this enum determine how a KnuthBendix instance measures the length \(d(AB, BC)\) of the overlap of two words \(AB\) and \(BC\).

See also

overlap_policy()

Members:

ABC :
\(d(AB, BC) = |A| + |B| + |C|\)

AB_BC :
\(d(AB, BC) = |AB| + |BC|\)

MAX_AB_BC :
\(d(AB, BC) = max(|AB|, |BC|)\)

property name¶

overlap_policy(self: _libsemigroups_pybind11.KnuthBendix, val: _libsemigroups_pybind11.KnuthBendix.overlap) → _libsemigroups_pybind11.KnuthBendix¶

Set the overlap policy.

Parameters: val (int) -- the maximum number of rules.
Returns: self.

report(self: _libsemigroups_pybind11.KnuthBendix) → bool¶

Check if it is time to report.

Parameters: None
Returns: A bool.

report_every(self: _libsemigroups_pybind11.KnuthBendix, 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.KnuthBendix) → None¶

Report why we stopped.

Parameters: None
Returns: (None)

rewrite(self: _libsemigroups_pybind11.KnuthBendix, arg0: str) → str¶

Rewrite a word.

Rewrites a copy of the string w rewritten according to the current rules in the KnuthBendix instance.

Parameters: w (str) -- the word to rewrite.
Returns: A copy of the argument w after it has been rewritten.

rules(self: _libsemigroups_pybind11.KnuthBendix) → Iterator¶: Returns an iterator to the generating pairs of the congruence.

run(self: _libsemigroups_pybind11.KnuthBendix) → None¶

Run the algorithm until it finishes. :Parameters: None

Returns: (None)

run_for(self: _libsemigroups_pybind11.KnuthBendix, 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.KnuthBendix, func: Callable[[], bool]) → None¶

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

Parameters: func (Callable[], bool) -- a function.
Returns: (None)

running(self: _libsemigroups_pybind11.KnuthBendix) → bool¶

Check if currently running.

Parameters: (None)
Returns: True if run() is in the process of running and False if it is not.