The Stephen class

Class for constructing a word graph of left factors a word in a finitely presented semigroup.

This page describes the class Stephen which implements Stephen’s procedure for constructing the WordGraph corresponding to the left factors of a word in a finitely presented semigroup or a finitely presented inverse semigroup. The algorithm implemented in this class is closely related to the Todd-Coxeter algorithm (as implemented in ToddCoxeter) and originates in [Ste87].

See also

Runner.

Important

The class Stephen has all the methods of the Runner class but, for boring technical reasons, is not a subclass of Runner. If thing is an instance of Stephen, then you can use thing as if it were an instance of Runner but isinstance(thing, Runner) will return False.

>>> from libsemigroups_pybind11 import (Stephen, stephen, Presentation,
... presentation)
>>> p = Presentation([0, 1])
>>> presentation.add_rule(p, [0, 0, 0], [0])
>>> presentation.add_rule(p, [1, 1, 1], [1])
>>> presentation.add_rule(p, [0, 1, 0, 1], [0, 0])
>>> s = Stephen(p)
>>> s.set_word([1, 1, 0, 1]).run()
>>> stephen.accepts(s, [1, 1, 0, 0, 1, 0])
True
>>> stephen.accepts(s, [])
False

Contents

Stephen	Class for constructing a word graph of left factors a word in a finitely presented semigroup.
Stephen.accept_state(…)	This function gets the accept state of the word graph.
Stephen.copy(…)	This function returns a copy of a Stephen object.
Stephen.init(…)	Initialize from a presentation.
Stephen.initial_state(…)	Get the initial state of the word graph.
Stephen.is_word_set(…)	Check if the initial word is set.
Stephen.presentation(…)	Get the input presentation.
Stephen.set_word(…)	Set the initial word.
Stephen.word(…)	Get the initial word.
Stephen.word_graph(…)	Get the word graph.

Full API

class Stephen

__init__(self: Stephen, p: Presentation) → None

This function constructs Stephen from a presentation.

Parameters:

p (Presentation) – the presentation.

accept_state(self: Stephen) → int

This function gets the accept state of the word graph. Running 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 node.

Return type:

int

Raises:

LibsemigroupsError – if no presentation was set at the construction or with init() or if no word was set with set_word().

Warning

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

copy(self: Stephen) → Stephen

This function returns a copy of a Stephen object.

Returns:

A copy.

Return type:

Stephen

init(self: Stephen, p: Presentation | InversePresentation) → Stephen

Initialize from a presentation.

This function puts a Stephen object back into the same state as if it had been newly constructed from the presentation p.

Parameters:

p (Presentation | InversePresentation) – the presentation.

Returns:

self.

Return type:

Stephen

initial_state(self: Stephen) → int

Get the initial state of the word graph.

Returns:

the node.

Return type:

int

is_word_set(self: Stephen) → bool

Check if the initial word is set.

Returns True if a word has been set with set_word() since the last presentation change and False otherwise.

Returns:

A bool.

Return type:

bool

presentation(self: Stephen) → Presentation | InversePresentation

Get the input presentation.

Returns:

A presentation.

Return type:

Presentation | InversePresentation

set_word(self: Stephen, word: list[int]) → Stephen

Set the initial word.

This function sets the word whose left factors, or equivalent words, are sought.

Parameters:

word (list[int]) – the word to be set.

Returns:

self.

Return type:

Stephen

Raises:

LibsemigroupsError – if any of the values in word are out of range, i.e. they do not belong to the alphabet of Stephen.presentation.

word(self: Stephen) → list[int]

Get the initial word.

Returns the word set by set_word().

Returns:

A word.

Return type:

list[int]

Raises:

LibsemigroupsError – if no presentation was set at the construction or with init() or if no word was set with set_word().

word_graph(self: Stephen) → WordGraph

Get the word graph.

This function returns the word graph in its present state. The algorithm implemented in this class is not triggered by calls to this function.

Returns:

A WordGraph.

Return type:

WordGraph

Raises:

LibsemigroupsError – if no presentation was set at the construction or with init() or if no word was set with set_word().