Defined in stephen.hpp.

This page contains documentation for some helper functions for the Stephen class. The helpers documented on this page all belong to the namespace stephen.

Functions
template<typename PresentationType>
bool	accepts (Stephen< PresentationType > &s, word_type const &w)
	Check if a word is accepted by a Stephen instance.

template<typename PresentationType>
Dot	dot (Stephen< PresentationType > &s)
	Returns a Dot object representing the Stephen word graph.

template<typename PresentationType>
bool	is_left_factor (Stephen< PresentationType > &s, word_type const &w)
	Check if a word is a left factor of Stephen::word.

template<typename PresentationType>
auto	left_factors (Stephen< PresentationType > &s)
	Returns a range object containing all the words (in short-lex order) that are left factors of Stephen::word.

template<typename PresentationType>
uint64_t	number_of_left_factors (Stephen< PresentationType > &s, size_t min=0, size_t max=POSITIVE_INFINITY)
	Returns the number of left factors with length in a given range.

template<typename PresentationType>
uint64_t	number_of_words_accepted (Stephen< PresentationType > &s, size_t min=0, size_t max=POSITIVE_INFINITY)
	Returns the number of words accepted with length in a given range.

template<typename PresentationType>
Stephen< PresentationType > &	set_word (Stephen< PresentationType > &s, word_type const &w)
	Set the initial word.

template<typename PresentationType>
Stephen< PresentationType > &	set_word_no_checks (Stephen< PresentationType > &s, word_type const &w)
	Set the initial word (no checks).

template<typename PresentationType>
auto	words_accepted (Stephen< PresentationType > &s)
	Returns a range object containing all words accepted by a Stephen instance in short-lex order.

Function Documentation

◆ accepts()

template<typename PresentationType>

bool accepts	(	Stephen< PresentationType > &	s,
		word_type const &	w )

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

For a Stephen<Presentation> instance, 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<InversePresentation> instance, 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.

Template Parameters

PresentationType the type of presentation defining the Stephen instance, must be derived from PresentationBase.

Parameters

s	the Stephen instance.
w	a const reference to the input word.

Returns: A bool.

Exceptions

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

Note: The interpretation of results returned by this function differs between Stephen<Presentation> and Stephen<InversePresentation>."

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

◆ dot()

template<typename PresentationType>

Dot dot ( Stephen< PresentationType > & s )

This function returns a Dot object representing the underlying word graph of the Stephen instance s.

Template Parameters

PresentationType the type of presentation defining the Stephen instance, must be derived from PresentationBase.

Parameters

s	the Stephen instance.

Returns: A Dot object.

◆ is_left_factor()

template<typename PresentationType>

bool is_left_factor	(	Stephen< PresentationType > &	s,
		word_type const &	w )

This function triggers the algorithm implemented in this class (if it hasn't been triggered already), and then returns true if it labels a path in Stephen::word_graph with source 0.

A word w labels such a path if and only if w is a left factor of Stephen::word in the semigroup defined by Stephen::presentation. Note that this is true for both Stephen<Presentation> and Stephen<InversePresentation> instances.

Template Parameters

PresentationType the type of presentation defining the Stephen instance, must be derived from PresentationBase.

Parameters

s	the Stephen instance.
w	a const reference to the input word.

Returns: A bool.

Exceptions

LibsemigroupsException 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..

◆ left_factors()

template<typename PresentationType>

auto left_factors ( Stephen< PresentationType > & s )

This function triggers the algorithm implemented in this class (if it hasn't been triggered already) and then returns a range object containing all the words (in short-lex order) that are left factors of Stephen::word.

Template Parameters

PresentationType the type of presentation defining the Stephen instance, must be derived from PresentationBase.

Parameters

s	the Stephen instance.

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

Exceptions

LibsemigroupsException 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..

See also: stephen::is_left_factor

◆ number_of_left_factors()

template<typename PresentationType>

uint64_t number_of_left_factors	(	Stephen< PresentationType > &	s,
		size_t	min = 0,
		size_t	max = POSITIVE_INFINITY )

This function triggers the algorithm implemented in this class (if it hasn't been triggered already) and then returns the 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 with source 0 and length in the range min to max.

Template Parameters

PresentationType the type of presentation defining the Stephen instance, must be derived from PresentationBase.

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).

Returns: A uint64_t.

Exceptions

LibsemigroupsException 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..

See also: stephen::is_left_factor

◆ number_of_words_accepted()

template<typename PresentationType>

uint64_t number_of_words_accepted	(	Stephen< PresentationType > &	s,
		size_t	min = 0,
		size_t	max = POSITIVE_INFINITY )

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<Presentation> instance this is the same as the number of words are equivalent to Stephen::word with length between min and max.

For a Stephen<InversePresentation> instance this is the same as the number of words \(w\) such that \(uu^{-1}w\) is equivalent to \(u\) with length between min and max, where \(u\) is Stephen::word.

Template Parameters

PresentationType the type of presentation defining the Stephen instance, must be derived from PresentationBase.

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).

Returns: A uint64_t.

Exceptions

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

Note: The interpretation of results returned by this function differs between Stephen<Presentation> and Stephen<InversePresentation>."

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

See also: stephen::accepts

◆ set_word()

template<typename PresentationType>

Stephen< PresentationType > & set_word	(	Stephen< PresentationType > &	s,
		word_type const &	w )

This function can be used to set the word whose left factors, or equivalent words, are sought. The input word is copied.

Parameters

w	a const reference to the input word.
s	the Stephen instance.

Returns: A reference to this.

Exceptions

LibsemigroupsException if the letters in w do not all belong to the alphabet of the presentation.

◆ set_word_no_checks()

template<typename PresentationType>

Stephen< PresentationType > & set_word_no_checks	(	Stephen< PresentationType > &	s,
		word_type const &	w )

This function can be used to set the word whose left factors, or equivalent words, are sought. The input word is copied.

Parameters

s	the Stephen instance.
w	a const reference to the input word.

Returns: A reference to this.

Warning: This function does not argument checking whatsoever. It assumes that all letters of w belong to the alphabet of presentation. Bad things may happen if this assumption does not hold.

◆ words_accepted()

template<typename PresentationType>

auto words_accepted ( Stephen< PresentationType > & s )

This function triggers the algorithm implemented in this class (if it hasn't been triggered already) and then returns a range object containing all words accepted by a Stephen instance in short-lex order.

Template Parameters

PresentationType the type of presentation defining the Stephen instance, must be derived from PresentationBase.

Parameters

s	the Stephen instance.

Returns: A range object containing all words accepted by s in short-lex order.

Exceptions

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

Note: The interpretation of results returned by this function differs between Stephen<Presentation> and Stephen<InversePresentation>."

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

See also: stephen::accepts

Functions

Function Documentation

◆ accepts()

◆ dot()

◆ is_left_factor()

◆ left_factors()

◆ number_of_left_factors()

◆ number_of_words_accepted()

◆ set_word()

◆ set_word_no_checks()

◆ words_accepted()