Kambites¶

On this page we describe the functionality relating to the algorithms for small overlap monoids by Kambites and the authors of libsemigroups.

>>> from libsemigroups_pybind11 import Kambites, POSITIVE_INFINITY
>>> k = Kambites()
>>> k.set_alphabet("abcd")
>>> k.add_rule("abcd", "accca");
>>> k.number_of_pieces(0) == POSITIVE_INFINITY
True
>>> k.number_of_pieces(1)
4
>>> k.small_overlap_class()
4
>>> k.normal_form("bbcabcdaccaccabcddd")
'bbcabcdaccaccabcddd'
>>> k.equal_to("bbcabcdaccaccabcddd", "bbcabcdaccaccabcddd")
True

`Kambites`	Overloaded function.
`Kambites.add_rule`	Overloaded function.
`Kambites.add_rules`	Add rules from a `FroidurePin` instance.
`Kambites.alphabet`	Overloaded function.
`Kambites.char_to_uint`	Convert a `char` to a `letter_type`.
`Kambites.dead`	Check if the runner is dead.
`Kambites.equal_to`	Overloaded function.
`Kambites.finished`	Check if the main algorithm, implemented in this class, has been run to completion or not.
`Kambites.froidure_pin`	Returns an isomorphic `FroidurePin` instance.
`Kambites.has_froidure_pin`	Check if an isomorphic `FroidurePin` instance is known.
`Kambites.has_identity`	Check if an identity has been set.
`Kambites.identity`	Returns the identity (if any).
`Kambites.inverses`	Returns the inverses (if any).
`Kambites.is_obviously_finite`	Check if the finitely presented semigroup is obviously finite.
`Kambites.is_obviously_infinite`	Check if the finitely presented semigroup is obviously infinite.
`Kambites.kill`	Stop running the main algorithm(s) (thread-safe).
`Kambites.normal_form`	Overloaded function.
`Kambites.number_of_normal_forms`	Returns the number of normal forms with length in a given range.
`Kambites.number_of_pieces`	Returns the minimum number of pieces required to factorise the \(i\)-th relation word.
`Kambites.number_of_rules`	Returns the number of rules.
`Kambites.report`	Check if it is time to report.
`Kambites.report_every`	Set the minimum elapsed time between reports.
`Kambites.report_why_we_stopped`	Report why we stopped.
`Kambites.rules`	Returns an iterator to the rules.
`Kambites.run`	Run the algorithm until it finishes.
`Kambites.run_for`	Run for a specified amount of time.
`Kambites.run_until`	Run until a nullary predicate returns `True` or `finished()`.
`Kambites.running`	Check if currently running.
`Kambites.set_alphabet`	Overloaded function.
`Kambites.set_identity`	Overloaded function.
`Kambites.set_inverses`	Set the inverses of letters in `alphabet()`.
`Kambites.size`	Returns the size of the finitely presented semigroup or `POSITIVE_INFINITY`.
`Kambites.small_overlap_class`	Get the small overlap class.
`Kambites.started`	Check if `run()` has been called at least once before.
`Kambites.stopped`	Check if the runner is stopped.
`Kambites.stopped_by_predicate`	Check if the main algorithm was, or should be, stopped by the nullary predicate passed as first argument to `run_until()`.
`Kambites.string_to_word`	Convert a string to a word.
`Kambites.timed_out`	Check if the main algorithm has or should timed out.
`Kambites.uint_to_char`	Convert a `int` to a `char`.
`Kambites.validate_letter`	Overloaded function.
`Kambites.validate_word`	Overloaded function.
`Kambites.word_to_string`	Convert a `List[int]` to a `str`.

class Kambites(*args, **kwargs)¶

Overloaded function.

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

add_rule(*args, **kwargs)¶

Overloaded function.

add_rule(self: _libsemigroups_pybind11.Kambites, rel: Tuple[List[int], List[int]]) -> None

Add a rule using a tuple of lists of ints.

Parameters

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

Returns

(None)
add_rule(self: _libsemigroups_pybind11.Kambites, u: str, v: str) -> None
Add a rule using strings.
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.Kambites, u: List[int], v: List[int]) -> None
Add a rule using two word_type const references.
Parameters
u (List[int]) - the left-hand side of the rule being added.

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

(None)

add_rules(self: _libsemigroups_pybind11.Kambites, S: libsemigroups::FroidurePinBase) → None¶

Add rules from a FroidurePin instance.

Parameters: S (FroidurePin) - a FroidurePin object representing a semigroup.
Returns: (None)

alphabet(*args, **kwargs)¶

Overloaded function.

alphabet(self: _libsemigroups_pybind11.Kambites, i: int) -> str

Returns the ith letter of the alphabet.

Parameters

i (int) - the index of the letter.

Returns

A string.
alphabet(self: _libsemigroups_pybind11.Kambites) -> str

Returns the alphabet.

Returns

A string.

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

Convert a char to a letter_type.

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

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.Kambites, 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.Kambites, 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.Kambites) → 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.Kambites) → libsemigroups::FroidurePinBase¶

Returns an isomorphic FroidurePin instance.

Returns: A FroidurePinBase.

has_froidure_pin(self: libsemigroups::FpSemigroupInterface) → bool¶

Check if an isomorphic FroidurePin instance is known.

Returns: A bool.

has_identity(self: libsemigroups::FpSemigroupInterface) → bool¶

Check if an identity has been set.

Returns: A bool.

identity(self: _libsemigroups_pybind11.Kambites) → str¶

Returns the identity (if any).

Returns: A string.

inverses(self: _libsemigroups_pybind11.Kambites) → str¶

Returns the inverses (if any).

Returns: A string.

is_obviously_finite(self: _libsemigroups_pybind11.Kambites) → bool¶

Check if the finitely presented semigroup is obviously finite.

Returns: A bool.

is_obviously_infinite(self: _libsemigroups_pybind11.Kambites) → bool¶

Check if the finitely presented semigroup is obviously infinite.

Returns: A bool.

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

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

Parameters: None
Returns: (None).

normal_form(*args, **kwargs)¶

Overloaded function.

normal_form(self: _libsemigroups_pybind11.Kambites, 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.Kambites, w: List[int]) -> List[int]

Returns a normal form for a word_type.

Parameters

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

Returns

The normal form of the parameter w, a value of type List[int].

number_of_normal_forms(self: _libsemigroups_pybind11.Kambites, 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_pieces(self: _libsemigroups_pybind11.Kambites, i: int) → int¶

Returns the minimum number of pieces required to factorise the \(i\)-th relation word.

Parameters: i (int) -- the index of the relation word
Returns: An int.

number_of_rules(self: libsemigroups::FpSemigroupInterface) → int¶

Returns the number of rules.

Returns: An int.

report(self: _libsemigroups_pybind11.Kambites) → bool¶

Check if it is time to report.

Parameters: None
Returns: A bool.

report_every(self: _libsemigroups_pybind11.Kambites, t: std::__1::chrono::duration<long long, std::__1::ratio<1l, 1000000000l> >) → 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.Kambites) → None¶

Report why we stopped.

Parameters: None
Returns: (None)

rules(self: _libsemigroups_pybind11.Kambites) → Iterator¶: Returns an iterator to the rules.

run(self: _libsemigroups_pybind11.Kambites) → None¶

Run the algorithm until it finishes. :Parameters: None

Returns: (None)

run_for(self: _libsemigroups_pybind11.Kambites, t: std::__1::chrono::duration<long long, std::__1::ratio<1l, 1000000000l> >) → 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.Kambites, func: std::__1::function<bool ()>) → None¶

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

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

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

Check if currently running.

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