Stephen helpers¶
Defined in stephen.hpp
.
This page contains the documentation for various helper functions for
manipulating Stephen
objects. All such functions are contained in
the namespace stephen
.
Contents¶
The return type of 

The return type of 

Check if a word is equivalent to 

Check if a word is a left factor of 

Returns an iterator pointing at the first word equivalent to


Returns an iterator pointing one past the last word equivalent to


Returns an iterator pointing at the first word (in shortlex order)
that is a left factor of 

Returns an iterator pointing one past the last word that is a left
factor of 

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

Returns the number of left factors with length in given range. 
Full API¶

namespace libsemigroups::stephen¶
Typedefs

using const_iterator_words_accepted = typename Stephen::digraph_type::const_pstislo_iterator¶
The return type of cbegin_words_accepted and cend_words_accepted.
This is the same as ActionDigraph::const_pstislo_iterator.

using const_iterator_left_factors = typename Stephen::digraph_type::const_pislo_iterator¶
The return type of cbegin_left_factors and cend_left_factors.
This is the same as ActionDigraph::const_pislo_iterator.
Functions

bool accepts(Stephen &s, word_type const &w)¶
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 wordw
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 source0
and target Stephen::accept_state.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.
 Parameters
s – the Stephen instance
w – a const reference to the input word.
 Throws
LibsemigroupsException – if no presentation was set at the construction of
s
or with Stephen::init. Returns
A
bool
.

bool is_left_factor(Stephen &s, word_type const &w)¶
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 wordw
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 source0
.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.
 Parameters
s – the Stephen instance
w – a const reference to the input word.
 Throws
LibsemigroupsException – if no presentation was set at the construction of
s
or with Stephen::init. Returns
A
bool
.

const_iterator_words_accepted cbegin_words_accepted(Stephen &s, size_t min = 0, size_t max = POSITIVE_INFINITY)¶
Returns an iterator pointing at the first word equivalent to Stephen::word in shortlex order.
This function triggers the algorithm implemented in this class (if it hasn’t been triggered already).
See also
ActionDigraph::cbegin_pstislo for more information about the iterators returned by this function.
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.
 Parameters
s – the Stephen instance
min – the minimum length of an equivalent word (default: 0)
max – the maximum length of an equivalent word (default: POSITIVE_INFINITY)
 Throws
LibsemigroupsException – if no presentation was set at the construction of
s
or with Stephen::init. Returns
A
const_iterator
.

const_iterator_words_accepted cend_words_accepted(Stephen &s)¶
Returns an iterator pointing one past the last word equivalent to Stephen::word.
See also
cbegin_words_accepted for more information.

const_iterator_left_factors cbegin_left_factors(Stephen &s, size_t min = 0, size_t max = POSITIVE_INFINITY)¶
Returns an iterator pointing at the first word (in shortlex 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).
See also
ActionDigraph::cbegin_pislo for more information about the iterators returned by this function.
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.
 Parameters
s – the Stephen instance
min – the minimum length of an equivalent word (default: 0)
max – the maximum length of an equivalent word (default: POSITIVE_INFINITY)
 Throws
LibsemigroupsException – if no presentation was set at the construction of
s
or with Stephen::init. Returns
A
const_iterator_left_factors
.

const_iterator_left_factors cend_left_factors(Stephen &s)¶
Returns an iterator pointing one past the last word that is a left factor of Stephen::word.
See also
cbegin_left_factors for more information.

uint64_t number_of_words_accepted(Stephen &s, size_t min = 0, size_t max = POSITIVE_INFINITY)¶
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 betweenmin
andmax
. This is the same as the number of paths in Stephen::word_graph (if Stephen::run has been called) with source0
, target Stephen::accept_state, and length in the rangemin
tomax
.See also
 Parameters
s – the Stephen instance.
min – the minimum length of a word (default: 0).
max – one more than the maximum length of a word (default: POSITIVE_INFINITY).
 Throws
LibsemigroupsException – if no presentation was set at the construction of
s
or with Stephen::init. Returns
A
uint64_t
.

uint64_t number_of_left_factors(Stephen &s, size_t min = 0, size_t max = POSITIVE_INFINITY)¶
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 betweenmin
andmax
. This is the same as the number of paths in Stephen::word_graph (if Stephen::run has been called) with source0
and length in the rangemin
tomax
.See also
 Parameters
s – the Stephen instance.
min – the minimum length of a word (default: 0).
max – one more than the maximum length of a word (default: POSITIVE_INFINITY).
 Throws
LibsemigroupsException – if no presentation was set at the construction of
s
or with Stephen::init.LibsemigroupsException – if no presentation was set at construction or with Stephen::init.
 Returns
A
uint64_t
.

using const_iterator_words_accepted = typename Stephen::digraph_type::const_pstislo_iterator¶