Stephen helpers¶

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

Contents¶

`accepts()`	Check if a word is equivalent to `Stephen.word()`.
`is_left_factor()`	Check if a word is a left factor of `Stephen.word()`.
`left_factors()`	Returns an iterator pointing at the first word (in short-lex order) that is a left factor of `Stephen.word()`.
`number_of_left_factors()`	Returns the number of left factors with length in given range.
`number_of_words_accepted()`	Returns the number of words accepted with length in a given range.
`words_accepted()`	Returns an iterator pointing at the first word equivalent to `Stephen.word()` in short-lex order.

Full API¶

accepts(s: _libsemigroups_pybind11.Stephen, w: List[int]) → bool¶

Check if a word is equivalent to 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 equivalent to Stephen.word() in the semigroup defined by Stephen.presentation(). A word is equivalent to Stephen.word() if it labels a path in Stephen.word_graph() with source c 0 and target Stephen.accept_state().

Parameters

s (Stephen) -- the Stephen instance.
w (List[int]) -- the input word.

Returns

True if the words is equivalent and False otherwise.

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.

is_left_factor(s: _libsemigroups_pybind11.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

True if w is a left factor of Stephen.word() and False if not.

Return type

bool

Raises

RuntimeError -- if no presentation was set at the construction of s or with Stephen.init().

Warning

The problem of determining whether a word is a left factor of another word in a finitely presented semigroup is undecidable in general, and this function may never terminate.

left_factors(s: _libsemigroups_pybind11.Stephen, min: int = 0, max: int = 18446744073709551614) → Iterator¶

Returns an iterator pointing at the first word (in short-lex order) that is a left factor 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
min (int) -- the minimum length of an equivalent word (default: 0)
max (int) -- the maximum length of an equivalent word (default: POSITIVE_INFINITY)

Returns

An iterator.

Raises

RuntimeError -- if no presentation was set at the construction of s or with Stephen.init().

Warning

The problem of determining whether a word is a left factor of another word in a finitely presented semigroup is undecidable in general, and this function may never terminate.

number_of_left_factors(s: _libsemigroups_pybind11.Stephen, min: int = 0, max: int = 18446744073709551614) → int¶

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 Stephen.run() has been called) with source 0 and length in the range min to max.

Parameters

s (Stephen) -- the Stephen instance.
min (int) -- the minimum length of a word (default: 0).
max (int) -- one more than the maximum length of a word (default: POSITIVE_INFINITY).

Returns

An int.

Raises

RuntimeError -- if no presentation was set at the construction of s or with Stephen.init().

number_of_words_accepted(s: _libsemigroups_pybind11.Stephen, min: int = 0, max: int = 18446744073709551614) → int¶

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

This function returns the number of words that are equivalent to 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 Stephen.run() has been called) with source 0, target Stephen.accept_state(), and length in the range min to max.

Parameters

s (Stephen) -- the Stephen instance.
min (int) -- the minimum length of a word (default: 0).
max (int) -- one more than the maximum length of a word (default: POSITIVE_INFINITY).

Returns

An int.

Raises

RuntimeError -- if no presentation was set at the construction of s or with Stephen.init().