Stephen¶

On this page we describe the functionality in libsemigroups_pybind11 relating to Stephen’s procedure for finitely presented semigroups. This class implements Stephen’s procedure for (possibly) constructing the word graph (ActionDigraph) corresponding to the left factors of a word in a finitely presented semigroup. The algorithm implemented in this class is closely related to the Todd-Coxeter algorithm (as implemented in ToddCoxeter) and originates in Applications of automata theory to presentations of monoids and inverse monoids by J. B. Stephen.

>>> from libsemigroups_pybind11 import Presentation, presentation, Stephen, action_digraph_helper, UNDEFINED
>>> p = Presentation([0, 1])
>>> presentation.add_rule_and_check(p, [0, 0, 0], [0])
>>> presentation.add_rule_and_check(p, [1, 1, 1], [1])
>>> presentation.add_rule_and_check(p, [0, 1, 0, 1], [0, 0])
>>> s = Stephen(p)
>>> s.set_word([1, 1, 0, 1]).run()
>>> s.word_graph().number_of_nodes()
7
>>> s.word_graph() == action_digraph_helper.make(
... 7,
... [
...   [UNDEFINED, 1],
...   [UNDEFINED, 2],
...   [3, 1],
...   [4, 5],
...   [3, 6],
...   [6, 3],
...   [5, 4],
... ])
True

Methods¶

`Stephen`	Overloaded function.
`Stephen.init`	Overloaded function.
`Stephen.accept_state`	The accept state of the word graph.
`Stephen.presentation`	The input presentation.
`Stephen.set_word`	Set the word.
`Stephen.word`	The word.
`Stephen.word_graph`	The word graph.

Methods inherited from Runner¶

`Stephen.dead`	Check if the runner is dead.
`Stephen.finished`	Check if the main algorithm, implemented in this class, has been run to completion or not.
`Stephen.kill`	Stop running the main algorithm(s) (thread-safe).
`Stephen.report`	Check if it is time to report.
`Stephen.report_every`	Set the minimum elapsed time between reports.
`Stephen.report_why_we_stopped`	Report why we stopped.
`Stephen.run`	Run the algorithm until it finishes.
`Stephen.run_for`	Run for a specified amount of time.
`Stephen.run_until`	Run until a nullary predicate returns `True` or `finished()`.
`Stephen.running`	Check if currently running.
`Stephen.started`	Check if `run()` has been called at least once before.
`Stephen.stopped`	Check if the runner is stopped.
`Stephen.stopped_by_predicate`	Check if the main algorithm was, or should be, stopped by the nullary predicate passed as first argument to `run_until()`.
`Stephen.timed_out`	Check if the main algorithm has or should timed out.

class Stephen(*args, **kwargs)¶

Overloaded function.

__init__(self: _libsemigroups_pybind11.Stephen, p: _libsemigroups_pybind11.PresentationWords) -> None

Construct from a presentation with relation words given by lists of integers.

Parameters

p (Presentation) - the presentation.

Raises

RunTimeError if p.validate() raises.

Raises

RunTimeError if p.alphabet().size() is 0.
__init__(self: _libsemigroups_pybind11.Stephen, p: _libsemigroups_pybind11.PresentationStrings) -> None

Construct from a presentation with relation words given by strings.

Parameters

p (Presentation) - the presentation.

Raises

RunTimeError if p.validate() raises.

Raises

RunTimeError if p.alphabet().size() is 0.
__init__(self: _libsemigroups_pybind11.Stephen, s: _libsemigroups_pybind11.Stephen) -> None

Copy a Stephen instance.

accept_state(self: _libsemigroups_pybind11.Stephen) → int¶

The accept state of the word graph.

This function triggers the algorithm implemented in this class (if it hasn't been triggered already), and then returns the accept state of the produced word graph.

Returns: the accept state
Return type: int
Raises: RuntimeError -- if no presentation was set at the construction of s or with Stephen.init().
Warning: The problem of determining whether two words are equal in a finitely presented semigroup is undecidable in general, and this function may never terminate.

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

Check if the runner is dead.

Parameters: None
Returns: A bool.

finished(self: _libsemigroups_pybind11.Stephen) → bool¶

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

Parameters: None
Returns: A bool.

init(*args, **kwargs)¶

Overloaded function.

init(self: _libsemigroups_pybind11.Stephen, p: _libsemigroups_pybind11.PresentationWords) -> _libsemigroups_pybind11.Stephen

Initialize from a presentation with relation words given by lists of integers.

Replaces the current value (if any) returned by Stephen.presentation() by the argument, and the state of the object is the same as if it had been newly constructed from the presentation p.

Parameters

p (Presentation) - the presentation.

Returns

self.

Raises

RunTimeError if p.validate() raises.

Raises

RunTimeError if p.alphabet().size() is 0.
init(self: _libsemigroups_pybind11.Stephen, p: _libsemigroups_pybind11.PresentationStrings) -> _libsemigroups_pybind11.Stephen

Initialize from a presentation with relation words given by strings.

Replaces the current value (if any) returned by Stephen.presentation() by the argument, and the state of the object is the same as if it had been newly constructed from the presentation p.

Parameters

p (Presentation) - the presentation.

Returns

self.

Raises

RunTimeError if p.validate() raises.

Raises

RunTimeError if p.alphabet().size() is 0.

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

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

Parameters: None
Returns: (None).

presentation(self: _libsemigroups_pybind11.Stephen) → _libsemigroups_pybind11.PresentationWords¶

The input presentation.

Returns: the input presentation
Return type: Presentation

report(self: _libsemigroups_pybind11.Stephen) → bool¶

Check if it is time to report.

Parameters: None
Returns: A bool.

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

Report why we stopped.

Parameters: None
Returns: (None)

run(self: _libsemigroups_pybind11.Stephen) → None¶

Run the algorithm until it finishes. :Parameters: None

Returns: (None)

run_for(self: _libsemigroups_pybind11.Stephen, 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.Stephen, func: Callable[[], 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.