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

const_iterator_words_accepted

The return type of cbegin_words_accepted() and cend_words_accepted().

const_iterator_left_factors

The return type of cbegin_left_factors() and cend_left_factors().

accepts()

Check if a word is equivalent to Stephen::word().

is_left_factor()

Check if a word is a left factor of Stephen::word().

cbegin_words_accepted()

Returns an iterator pointing at the first word equivalent to Stephen::word() in short-lex order.

cend_words_accepted()

Returns an iterator pointing one past the last word equivalent to Stephen::word().

cbegin_left_factors()

Returns an iterator pointing at the first word (in short-lex order) that is a left factor of Stephen::word().

cend_left_factors()

Returns an iterator pointing one past the last word that is a left factor of Stephen::word().

number_of_words_accepted()

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

number_of_left_factors()

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

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

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

See also

ActionDigraph::number_of_paths.

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

See also

ActionDigraph::number_of_paths.

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
Returns

A uint64_t.