Stephen helpers

This page contains the documentation for various helper functions for manipulating Stephen objects.

Contents

accepts(…)

Check if a word is accepted by a Stephen instance.

dot(…)

Return a Dot object representing the underlying word graph of the Stephen object s.

is_left_factor(…)

Check if a word is a left factor of Stephen.word.

left_factors(…)

Returns a Paths object containing all the words (in short-lex order) that are left factors of Stephen.word.

number_of_left_factors(…)

Returns the number of left factors with length in a given range.

number_of_words_accepted(…)

Returns the number of words accepted with length in a given range.

words_accepted(…)

Returns a Paths object containing all words accepted by a Stephen instance in short-lex order.

Full API

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

stephen.accepts(s: Stephen, w: list[int]) → bool

Check if a word is accepted by a Stephen instance.

This function triggers the algorithm implemented in this class (if it hasn’t been triggered already), and then returns True if the input word w labels a path in Stephen.word_graph with source 0 and target Stephen.accept_state.

For a Stephen instance constructed from a Presentation, a word w is accepted if and only if w is equivalent to Stephen.word in the semigroup defined by Stephen.presentation.

For a Stephen instance constructed from a InversePresentation, a word w is accepted if and only if \(uu^{-1}w\) is equivalent to \(u\) in the semigroup defined by Stephen.presentation, where \(u\) is the value of Stephen.word.

Parameters:

  • s (Stephen) – the Stephen instance

  • w (list[int]) – the input word.

Returns:

A bool.

Return type:

bool

Raises:

LibsemigroupsError – if no presentation was set at the construction of s or with Stephen.init or if no word was set with Stephen.set_word.

Warning

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

stephen.dot(s: Stephen) → Dot

Return a Dot object representing the underlying word graph of the Stephen object s.

Parameters:

s (Stephen) – the Stephen object.

Returns:

A Dot object.

Return type:

Dot

stephen.is_left_factor(s: Stephen, w: list[int]) → bool

Check if a word is a left factor of Stephen.word.

This function triggers the algorithm implemented in this class (if it hasn’t been triggered already), and then returns True if the input word w is a left factor of Stephen.word in the semigroup defined by Stephen.presentation . A word is a left factor of Stephen.word if it labels a path in Stephen.word_graph with source 0.

Parameters:

  • s (Stephen) – the Stephen instance.

  • w (list[int]) – the input word.

Returns:

A bool.

Return type:

bool

Raises:

LibsemigroupsError – if no presentation was set at the construction of s or with Stephen.init or if no word was set with Stephen.set_word.

Warning

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

stephen.left_factors(s: Stephen) → Paths

Returns a Paths object containing all the words (in short-lex order) that are left factors of Stephen.word.

This function triggers the algorithm implemented in this class (if it hasn’t been triggered already).

Parameters:

s (Stephen) – the Stephen instance

Returns:

A Paths object containing all the words (in short-lex order) that are left factors of Stephen.word.

Return type:

Paths

Raises:

LibsemigroupsError – if no presentation was set at the construction of s or with Stephen.init or if no word was set with Stephen.set_word.

Warning

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

stephen.number_of_left_factors(s: Stephen, min: int = 0, max: int | PositiveInfinity = POSITIVE_INFINITY) → int | PositiveInfinity

Returns the number of left factors with length in a given range.

This function returns the number of left factors of the Stephen.word in the instance s with length between min and max. This is the same as the number of paths in Stephen.word_graph (if the inherited Runner.run method of s has been called) with source 0 and length in the range min to max.

Parameters:
Returns:

An int or POSITIVE_INFINITY.

Return type:

int | PositiveInfinity

Raises:

LibsemigroupsError – if no presentation was set at the construction of s or with Stephen.init or if no word was set with Stephen.set_word.

Warning

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

stephen.number_of_words_accepted(s: Stephen, min: int = 0, max: int | PositiveInfinity = POSITIVE_INFINITY) → int | PositiveInfinity

Returns the number of words accepted with length in a given range.

This function triggers the algorithm implemented in this class (if it hasn’t been triggered already) and then returns the the number of paths in Stephen.word_graph with source 0, target Stephen.accept_state, and length in the range min to max.

For a Stephen instance constructed from a Presentation this is the same as the number of words that are equivalent to Stephen.word with length between min and max.

For a Stephen instance constructed from a InversePresentation, this is the same as the number of words w such that \(uu^{-1}w\) is equivalent to \(u\) in the semigroup defined by Stephen.presentation, where \(u\) is the value of Stephen.word.

Parameters:
Returns:

The number of words accepted.

Return type:

int | PositiveInfinity

Raises:

LibsemigroupsError – if no presentation was set at the construction of s or with Stephen.init or if no word was set with Stephen.set_word.

Warning

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

stephen.words_accepted(s: Stephen) → Paths

Returns a Paths object containing all words accepted by a Stephen instance in short-lex order.

This function triggers the algorithm implemented in this class (if it hasn’t been triggered already).

Parameters:

s (Stephen) – the Stephen instance

Returns:

A Paths object containing all words equivalent to Stephen.word in short-lex order.

Return type:

Paths

Raises:

LibsemigroupsError – if no presentation was set at the construction of s or with Stephen.init or if no word was set with Stephen.set_word.

Warning

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