awali::sttc Namespace Reference

Namespace for the static layer of Awali. More...

Namespaces
	ctx
	Namespace containing all available contexts (weigh sets, label sets, etc.).
	deprecated
	detail_info
	internal
	Implementation details of static layer (not stable).
	rat
	Namespace about static rational expressions.

Data Structures
class	b
	The Boolean semring. More...
class	c
	The semiring of complex numbers. More...
class	char_letters
	helper for manipulations of char letters More...
class	context
	carries the algebraic settings of automata More...
struct	empty_t
	Empty labels, for LAO. More...
struct	exp_stats_t
	gathers informations on some rational expression More...
class	f2
	The field F2. More...
class	history_base
	base type for history of automata More...
class	int_letters
	helper for manipulations of int letters More...
struct	labels_are_letters
	marker type for labelsets where labels are letters More...
struct	labels_are_nullable
	marker type for labelsets where labels are nullable More...
struct	labels_are_one
	marker type for labelsets where labels are one More...
struct	labels_are_ratexps
	marker type for labelsets where labels are rational expressions More...
struct	labels_are_tuples
	marker type for labelsets where labels are tuples More...
struct	labels_are_words
	marker type for labelsets where labels are words More...
struct	labelset_trait
	trait that computes the related types of a labelset More...
struct	labelset_trait< letterset< T > >
	specialisation of labelset_trait for letterset More...
struct	labelset_trait< nullableset< T > >
	specialisation of labelset_trait for nullableset More...
struct	labelset_trait< oneset >
	specialisation of labelset_trait for oneset More...
struct	labelset_trait< tupleset< Ts... > >
	specialisation of labelset_trait for tupleset More...
struct	labelset_trait< wordset< T > >
	specialisation of labelset_trait for wordset More...
class	letterset
	Implementation of labels are letters. More...
class	maxmin
	The max-min semiring over floating numbers. More...
class	n
	The semiring of Natural numbers. More...
class	nn
	The semiring of natural numbers bounded by K. More...
class	no_history
	specialisation of history_base More...
class	noo
	The semiring of extended natural numbers. More...
class	nullableset
	Implementation of labels are nullables (letter or empty). More...
class	oneset
	Implementation of labels are ones: there is a single instance of label. More...
class	pair_letters
	helper for manipulations of pair letters More...
class	partition_history
	specialisation of history_base More...
class	pmax
	The semiring of maximum probabilities. More...
class	polynomialset
	Linear combination of labels: map labels to weights. More...
class	q
	The semiring of rational numbers. More...
class	r
	The semiring of floating Numbers. More...
class	ratexp_history
	specialisation of history_base More...
class	set_alphabet
	objets that represent the alphabets of letters as char More...
class	single_history
	specialisation of history_base More...
class	string_history
struct	test_acyclic
struct	transition_tuple
struct	transition_tuple< State, Label, bool >
class	tuple_history
	An automaton whose states are tuples of states of automata. More...
class	tupleset
	A ValueSet which is a Cartesian product of ValueSets. More...
struct	variadic_mul_mixin
	Provide a variadic mul on top of a binary mul(), and one(). More...
class	wordset
	Implementation of labels are words. More...
class	z
	The semiring of Integers. More...
class	zmax
	The Z-max-plus semiring. More...
class	zmin
	The Z-min-plus semiring. More...
class	zz
	The cyclic semiring with characteristic N. More...

Typedefs
template<typename ValueSet >
using	context_t_of = typename internal::context_t_of_impl< internal::base_t< ValueSet > >::type
	Helper to retrieve the type of the context of a value set. More...
template<typename... ValueSets>
using	join_t = decltype(join(std::declval< ValueSets >()...))
	Computation of the join of some value sets. More...
template<typename ValueSet >
using	label_t_of = typename internal::label_t_of_impl< internal::base_t< ValueSet > >::type
	Helper to retrieve the type of the labels of a value set. More...
template<typename ValueSet >
using	labelset_t_of = typename internal::labelset_t_of_impl< internal::base_t< ValueSet > >::type
	Helper to retrieve the type of the labelset of a value set. More...
template<typename... ValueSets>
using	labelset_types = internal::labelset_types< void, ValueSets... >
template<typename... ValueSets>
using	meet_t = decltype(meet(std::declval< ValueSets >()...))
	Computation of the meet of some value sets. More...
template<typename Context >
using	mutable_automaton = std::shared_ptr< internal::mutable_automaton_impl< Context > >
template<typename Context >
using	not_nullable_of = context< typename labelset_trait< typename Context::labelset_t >::not_nullable_t, typename Context::weightset_t >
template<typename Context >
using	nullable_of = context< typename labelset_trait< typename Context::labelset_t >::nullable_t, typename Context::weightset_t >
template<typename Aut >
using	pair_automaton = std::shared_ptr< internal::pair_automaton_impl< Aut > >
template<typename Aut >
using	partition_automaton = std::shared_ptr< internal::partition_automaton_impl< Aut > >
	A subset automaton as a shared pointer. More...
template<typename Aut >
using	permutation_automaton = std::shared_ptr< internal::permutation_automaton_impl< Aut > >
	A permutation automaton as a shared pointer. More...
template<typename Aut >
using	ratexp_automaton = std::shared_ptr< internal::ratexp_automaton_impl< Aut > >
	A ratexp automaton as a shared pointer. More...
template<typename Context >
using	ratexp_context_of = context< typename labelset_trait< typename Context::labelset_t >::ratlabelset_t, typename Context::weightset_t >
template<typename Context >
using	ratexpset = variadic_mul_mixin< rat::ratexpset_impl< Context > >
template<typename Context >
using	ratexpset_of = ratexpset< ratexp_context_of< Context > >
template<typename Aut , typename Lifted = internal::lifted_automaton_t<Aut>>
using	state_chooser_t = std::function< state_t(const Lifted &)>
	A state (inner) from an automaton. More...
template<typename... Auts>
using	tuple_automaton = std::shared_ptr< internal::tuple_automaton_impl< Auts... > >
	A product automaton as a shared pointer. More...
template<typename ValueSet >
using	weight_t_of = typename internal::weight_t_of_impl< internal::base_t< ValueSet > >::type
	Helper to retrieve the type of the weights of a value set. More...
template<typename ValueSet >
using	weightset_t_of = typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type
	Helper to retrieve the type of the weightset of a value set. More...

Functions
template<typename Aut >
Aut::element_type::automaton_nocv_t	accessible (const Aut &aut, bool keep_history=true)
	Accessible subautomaton. More...
template<typename Aut >
void	accessible_here (Aut &aut)
	In-place accessible subautomaton. More...
template<typename Aut >
std::set< state_t >	accessible_states (const Aut &aut, bool include_pre_post=false)
	List of accessible states. More...
template<typename Aut >
weight_t_of< Aut >	add_epsilon_trans (Aut a, state_t src, state_t dst, weight_t_of< Aut > w)
	Helper to add an epsilon transition. More...
template<typename Aut >
weight_t_of< Aut >	add_epsilon_trans (const Aut a, state_t src, state_t dst)
	Helper to add an epsilon transition. More...
template<typename Aut >
void	add_path (Aut &aut, state_t p, state_t q, const std::string &s, bool strict_alphabet=true)
	adds a subautomaton realizing the series s between states p and q of aut. More...
template<typename Aut >
auto	add_path (Aut &aut, state_t p, state_t q, const typename context_t_of< Aut >::ratexp_t &exp) -> typename std::enable_if<!labelset_t_of< Aut >::has_one(), void >::type
	adds a subautomaton realizing the series exp between states p and q of aut. More...
template<typename Aut >
auto	allow_words (const Aut &aut, bool keep_history=true) -> typename internal::allowworder< Aut >::ret_automaton_t
	Turns the automaton into an automaton labeled with words. More...
template<typename Aut0 , typename Aut2 >
bool	are_equivalent (const Aut0 &aut1, const Aut2 &aut2)
	Tests if aut1 and aut2 are equivalent. More...
template<typename Aut1 , typename Aut2 >
bool	are_isomorphic (const Aut1 &a1, const Aut2 &a2)
	tests whether two automata are isomorphic More...
template<typename Automaton , unsigned version = version::fsm_json>
json_ast_t	aut_to_ast (Automaton aut, json_ast_t extra_metadata=json_ast::empty(), bool full=false)
template<typename Aut , typename Context = ratexpset_of<context_t_of<Aut>>>
Context::ratexp_t	aut_to_exp (const Aut &a)
	Default state elimination algorithm. More...
template<typename Aut , typename Context = ratexpset_of<context_t_of<Aut>>>
Context::ratexp_t	aut_to_exp (const Aut &a, const state_chooser_t< Aut > &next_state)
	Generic state elimination algorithm. More...
template<typename Aut , typename Context = ratexpset_of<context_t_of<Aut>>>
Context::ratexp_t	aut_to_exp_in_order (const Aut &a)
	Basic state elimination algorithm. More...
std::string	bracketed (std::istream &i, const char lbracket, const char rbracket)
	An narrow-char stream that discards the output. More...
template<typename Ctx >
mutable_automaton< Ctx >	cerny (const Ctx &ctx, unsigned num_states)
	Cerny automata are automata whose synchronizing word length is always (n - 1)^2, the upper bound of the Cerny's conjecture. More...
template<typename Aut >
Aut	chain (const Aut &aut, unsigned min, int max)
	chains automata to compute powers of a series More...
template<typename RatExpSet >
RatExpSet::ratexp_t	chain (const RatExpSet &rs, const typename RatExpSet::ratexp_t &r, unsigned min, int max)
	computes powers of rational exp More...
template<typename Aut >
void	change_alphabet (Aut &aut, const std::set< typename labelset_t_of< Aut >::letter_t > &letters, bool del_unvalid_transitions=true)
	Change letters in the alphabet of the automaton. More...
template<typename Aut >
Aut::element_type::automaton_nocv_t	coaccessible (const Aut &aut, bool keep_history=true)
	Coaccessible subautomaton. More...
template<typename Aut >
void	coaccessible_here (Aut &aut)
	In-place coaccessible subautomaton. More...
template<typename Aut >
std::set< state_t >	coaccessible_states (const Aut &aut, bool include_pre_post=false)
	List of coaccessible states. More...
template<typename Aut >
auto	codeterminize (const Aut &aut, bool keep_history=true) -> mutable_automaton< context_t_of< Aut >>
	Co-determinization of the automaton. More...
template<typename Aut >
auto	compact (const Aut &aut, bool keep_history=true) -> typename internal::allowworder< Aut >::ret_automaton_t
	Compacts non branching paths. More...
template<typename Aut >
void	compact_here (Aut &aut)
	Compacts non branching paths. More...
template<typename Aut , typename Context = context_t_of<Aut>>
Aut	compact_thompson (const Context &ctx, const typename Context::ratexp_t &exp, bool keep_history=true)
	builds a compact variant of the Thompson automaton More...
template<typename RatExpSet >
mutable_automaton< sttc::nullable_of< typename RatExpSet::context_t > >	compact_thompson (const RatExpSet &rs, const typename RatExpSet::ratexp_t &exp, bool keep_history=true)
	builds a compact variant of the Thompson automaton More...
template<typename Aut >
auto	complement (const Aut &aut, bool keep_history=true) -> decltype(copy(aut))
	Complementation of a deterministic complete automaton. More...
template<typename Aut >
Aut	complement_here (Aut &aut)
	Complementation of a deterministic complete automaton. More...
template<typename Aut >
auto	complete (const Aut &aut, bool keep_history=true) -> decltype(copy(aut, keep_history))
	Completion of a deterministic automaton. More...
template<typename Aut >
Aut &	complete_here (Aut &aut)
	Completion of a deterministic automaton. More...
template<typename Aut >
const std::vector< std::unordered_set< state_t > >	components (const Aut &aut)
	Find all strongly connected components of aut. More...
template<typename TDC1 , typename TDC2 >
auto	compose (const TDC1 &tdc1, const TDC2 &tdc2, bool keep_history=true) -> typename internal::composer< TDC1, TDC2, 1, 0 >::automaton_t
	Composition of two transducers. More...
template<size_t I, size_t J, typename TDC1 , typename TDC2 >
auto	composeIJ (TDC1 &tdc1, TDC2 &tdc2, bool keep_history=true) -> typename internal::composer< TDC1, TDC2, I, J >::automaton_t
	Composition of two transducers on given tapes. More...
template<typename Aut1 , typename Aut2 >
auto	concatenate (const Aut1 &aut1, const Aut2 &aut2) -> decltype(join_automata(aut1, aut2))
	Concatenates two automata. More...
template<typename ValueSet >
ValueSet::value_t	concatenate (const ValueSet &vs, const typename ValueSet::value_t &lhs, const typename ValueSet::value_t &rhs)
	wrapper for the multiplication of values More...
template<typename A , typename B >
A &	concatenate_here (A &res, const B &aut)
	Concatenation of an automaton to another one. More...
template<typename Aut >
std::pair< Aut, std::pair< std::unordered_map< state_t, unsigned int >, std::vector< std::vector< state_t > > > >	condensation (Aut aut)
	Condense each strongly connected component to a state. More...
template<typename RatExpSet >
weight_t_of< RatExpSet >	constant_term (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e)
template<typename ValueSet , typename... Args>
auto	conv (const ValueSet &vs, const std::string &str, Args &&... args) -> decltype(vs.conv(std::declval< std::istream & >(), std::forward< Args >(args)...))
	Parse str via vs.conv. More...
template<typename AutIn , typename AutOut = typename AutIn::element_type::automaton_nocv_t>
AutOut	copy (const AutIn &input, bool keep_history=true, bool transpose=false)
	A copy of input. More...
template<typename AutIn , typename AutOut = typename AutIn::element_type::automaton_nocv_t>
AutOut	copy (const AutIn &input, const std::set< state_t > &keep, bool keep_history=true, bool transpose=false)
	A copy of input keeping only its states that are members of keep. More...
template<typename AutIn , typename AutOut = typename AutIn::element_type::automaton_nocv_t, typename Pred >
AutOut	copy (const AutIn &input, Pred keep_state, bool keep_history=true, bool transpose=false)
	A copy of input keeping only its states that are accepted by keep_state. More...
template<typename AutIn , typename AutOut >
void	copy_into (const AutIn &in, AutOut &out, bool keep_history=true, bool transpose=false)
template<typename AutIn , typename AutOut , typename Pred >
void	copy_into (const AutIn &in, AutOut &out, Pred keep_state, bool keep_history=true, bool transpose=false)
	Copy an automaton. More...
template<typename AutIn , typename AutOut >
void	copy_support (const AutIn &in, AutOut &out, bool keep_history=true)
template<typename AutIn , typename AutOut , typename Pred >
void	copy_support (const AutIn &in, AutOut &out, Pred keep_state, bool keep_history=true)
template<typename Aut >
bool	cycle_identity (const std::unordered_set< state_t > &c, const Aut &aut)
	Check the weight of two states on this component is unique. More...
template<typename Aut >
std::ostream &	daut (const Aut &aut, std::ostream &out)
	Output in 'daut' format. More...
template<typename Aut >
void	del_epsilon_trans (Aut a, state_t src, state_t dst)
	Helper to delete an epsilon transition. More...
template<typename RatExpSet >
rat::ratexp_polynomial_t< RatExpSet >	derivation (const RatExpSet &rs, const rat::ratexp_polynomial_t< RatExpSet > &p, label_t_of< RatExpSet > a, bool breaking=false)
	Derive a polynomial of ratexps wrt to a letter. More...
template<typename RatExpSet >
rat::ratexp_polynomial_t< RatExpSet >	derivation (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e, const typename sttc::labelset_trait< typename RatExpSet::labelset_t >::wordset_t::word_t &word, bool breaking=false)
	Derive a ratexp wrt to a word. More...
template<typename RatExpSet >
rat::ratexp_polynomial_t< RatExpSet >	derivation (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e, label_t_of< RatExpSet > a, bool breaking=false)
	Derive a ratexp wrt to a letter. More...
template<typename RatExpSet >
mutable_automaton< typename RatExpSet::context_t >	derived_term (const RatExpSet &rs, const typename RatExpSet::ratexp_t &r, bool breaking=false, bool keep_history=true)
	Derive a ratexp wrt to a string. More...
template<typename Aut >
auto	determinize (const Aut &a, bool keep_history=true) -> mutable_automaton< context_t_of< Aut >>
	Determinization of the automaton. More...
template<typename Lhs , typename Rhs >
Lhs::element_type::automaton_nocv_t	difference (const Lhs &aut1, const Rhs &aut2)
	Computes an automaton that accepts every word accepted by aut1 which is not accepted by aut2. More...
template<typename Context >
mutable_automaton< Context >	divkbaseb (const Context &ctx, unsigned divisor, unsigned base)
	Returns an automaton which recognizes numbers in the given base which are multiple of divisor. More...
template<typename Aut >
std::ostream &	dot (const Aut &aut, std::ostream &out, bool dot2tex=false, bool keep_history=true, bool horizontal=true)
template<class Context >
mutable_automaton< Context >	double_ring (const Context &ctx, unsigned n, const std::vector< unsigned > &finals)
	Returns a double ring automaton with n states. More...
template<typename RatExpSet >
mutable_automaton< context< ctx::law_char, b > >	draw_exp (const RatExpSet &rs, const typename RatExpSet::ratexp_t &exp)
void	eat (std::istream &is, char c)
	Check lookahead character and advance. More...
void	eat (std::istream &is, const std::string &expect)
	Check lookahead string and advance. More...
template<typename Aut >
std::ostream &	efsm (const Aut &aut, std::ostream &out)
	Format automaton to EFSM format, based on FSM format. More...
template<typename Automaton >
internal::enumerater< Automaton >::polynomial_t	enumerate (const Automaton &aut, unsigned max_length)
	Gives the weight associated with each word shorter than max_length by aut. More...
template<class RatExpSet >
RatExpSet::ratexp_t	equals (const RatExpSet &rs, const typename RatExpSet::ratexp_t &v)
template<typename Aut >
auto	eval (const Aut &a, const typename labelset_trait< labelset_t_of< Aut >>::wordset_t::word_t &w, bool check_alphabet=true) -> weight_t_of< Aut >
template<typename Aut , typename Tdc >
auto	eval_tdc (const Aut &aut, const Tdc &tdc, bool keep_history=true) -> decltype(projection< 1 >(tdc))
	Evaluation of an automaton by a transducer. More...
template<typename Tdc >
auto	eval_words_in_tdc (const Tdc &tdc, const typename internal::select< labelset_t_of< Tdc >, 0 >::labelset_t::word_t &w1, const typename internal::select< labelset_t_of< Tdc >, 1 >::labelset_t::word_t &w2) -> weight_t_of< Tdc >
template<typename RatExpSet >
exp_stats_t	exp_stats (const RatExpSet &rs, const typename RatExpSet::ratexp_t &exp)
	computes some statistics on a rational expression More...
template<typename RatExpSet >
RatExpSet::value_t	expand (const RatExpSet &rs, const typename RatExpSet::value_t &e)
	Expanding a typed ratexp shared_ptr. More...
template<typename Aut >
auto	explore_by_length (const Aut &aut, unsigned depth) -> mutable_automaton< context_t_of< Aut >>
	Exploration of the automaton up to a given depth. More...
template<typename Aut >
auto	explore_with_bound (const Aut &aut, typename weightset_t_of< Aut >::value_t bound) -> mutable_automaton< context_t_of< Aut >>
	Exploration of the automaton up to a given bound. More...
template<typename Aut >
Aut::element_type::automaton_nocv_t	factor (const Aut &a, bool keep_history=true)
template<typename Aut >
void	factor_here (Aut &a)
	Make each useful state both initial and final. More...
template<typename Aut >
std::ostream &	fado (const Aut &aut, std::ostream &out)
ATTRIBUTE_NORETURN void	fail_reading (std::istream &is, std::string explanation)
	Throw an exception after failing to read from is. More...
template<typename Set , typename Aut >
void	fill_with_accessible_states (Set &res, const Aut &aut, bool include_pre_post=false)
template<typename Set , typename Aut >
void	fill_with_coaccessible_states (Set &res, const Aut &aut, bool include_pre_post=false)
template<typename ValueSet , typename... Args>
auto	format (const ValueSet &vs, const typename ValueSet::value_t &v, Args &&... args) -> std::string
	Format v via vs.print. More...
template<typename Aut >
polynomialset< context_t_of< Aut > >::value_t	get_entry (const Aut &aut, state_t s, state_t d)
	The entry between two states of an automaton. More...
ctx::lan_char::value_t	get_epsilon ()
	Helper to get the value of epsilon. More...
std::string	get_file_contents (const std::string &file)
	Return the contents of file. More...
template<typename L >
auto	get_letterset (const L &labelset) -> typename labelset_trait< L >::letterset_t
template<typename LS , typename WS >
auto	get_letterset_context (const context< LS, WS > &ctx) -> context< typename labelset_trait< LS >::letterset_t, WS >
template<typename Context >
auto	get_not_nullable_context (const Context &ctx) -> not_nullable_of< Context >
template<typename L >
auto	get_not_nullableset (const L &labelset) -> typename labelset_trait< L >::not_nullable_t
template<typename Context >
auto	get_nullable_context (const Context &ctx) -> nullable_of< Context >
template<typename L >
auto	get_nullableset (const L &labelset) -> typename labelset_trait< L >::nullable_t
template<typename Context >
ratexp_context_of< Context >	get_rat_context (const Context &ctx)
template<typename AUTOMATON >
auto	get_ratexpset (AUTOMATON &aut) -> ratexpset_of< context_t_of< AUTOMATON >>
template<typename L >
auto	get_ratlabelset (const L &labelset) -> typename labelset_trait< L >::ratlabelset_t
template<typename L2 >
set_alphabet< L2 >	get_union (const set_alphabet< L2 > &lhs, const set_alphabet< L2 > &rhs)
template<typename L >
auto	get_wordset (const L &labelset) -> typename labelset_trait< L >::wordset_t
template<typename LS , typename WS >
auto	get_wordset_context (const context< LS, WS > &ctx) -> context< typename labelset_trait< LS >::wordset_t, WS >
template<typename Aut >
std::ostream &	grail (const Aut &aut, std::ostream &out)
template<typename Aut >
bool	has_twins_property (const Aut &aut)
	Whether aut has the twins property. More...
template<typename Aut >
void	hopcroft_det (const Aut &aut, std::vector< std::vector< state_t > > &states_in_part)
	minimization with Hopcroft for incomplete deterministic automata More...
template<typename Aut >
unsigned	hopcroft_quotient (const Aut &aut, std::vector< std::list< state_t > > &states_in_part, bool cancellative=false)
template<typename Tdc >
auto	images (const Tdc &in, bool keep_history=true) -> typename internal::imagers< Tdc >::out_automaton_t
	Projection of last tapes of a transducer. More...
template<typename Aut >
bool	in_situ_remover (Aut &aut, bool prune=true)
	Blindly eliminate epsilon transitions without checking for the validity of the automaton. More...
template<typename Lhs , typename Rhs >
auto	infiltration (const Lhs &lhs, const Rhs &rhs, bool keep_history=true) -> decltype(join_automata(lhs, rhs))
	Build the (accessible part of the) infiltration. More...
template<class A >
std::ostream &	info (const A &aut, std::ostream &out, bool detailed=false)
template<class RatExpSet >
void	info (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e, std::ostream &o)
template<typename L2 >
set_alphabet< L2 >	intersection (const set_alphabet< L2 > &lhs, const set_alphabet< L2 > &rhs)
template<typename Aut >
auto	inverse (const Aut &aut) -> decltype(::sttc::copy(aut))
template<typename Aut >
Aut &	inverse_here (Aut &aut)
	Inverse the weight of all edges of aut. More...
template<typename Aut >
bool	is_accessible (const Aut &aut)
	Test whether every state of the automaton is accessible. More...
template<typename Aut >
ATTRIBUTE_CONST bool	is_acyclic (const Aut &aut)
template<typename Aut >
bool	is_ambiguous (const Aut &aut)
template<typename Aut >
bool	is_coaccessible (const Aut &aut)
	Test whether every state of the automaton is coaccessible. More...
template<typename Aut >
bool	is_complete (const Aut &aut)
	Whether aut is complete. More...
template<typename Aut >
bool	is_congruence (const Aut &aut, const std::vector< std::vector< state_t >> &partition)
template<class Aut >
bool	is_deterministic (const Aut &aut)
	tests whether the automaton is deterministic More...
template<typename Aut >
bool	is_empty (const Aut &aut)
	Test whether the automaton has no state. More...
template<typename Aut >
ATTRIBUTE_CONST bool	is_eps_acyclic (const Aut &aut)
template<typename Labelset >
bool	is_epsilon (const typename Labelset::value_t &l)
	Helper to test if a label is epsilon. More...
bool	is_epsilon (ctx::lan_char::value_t v)
template<typename WS >
constexpr bool	is_finite (const WS &ws)
template<typename Tdc >
bool	is_functional (Tdc &transducer)
template<typename WS >
constexpr bool	is_locally_finite (const WS &ws)
template<typename Aut >
bool	is_normalized (const Aut &a)
template<unsigned I, typename Tdc >
bool	is_of_finite_image (const Tdc &tdc)
	Check whether the image of every word is finite. More...
template<typename Aut >
bool	is_proper (const Aut &aut) ATTRIBUTE_CONST
	Test whether an automaton is proper. More...
template<size_t I, typename Tdc >
bool	is_proper_tape (const Tdc &tdc)
template<typename Aut1 , typename Aut2 >
bool	is_quotient (const Aut1 &a1, const Aut2 &a2)
template<typename Tdc >
bool	is_realtime (const Tdc &tdc)
template<class Aut >
bool	is_sequential (const Aut &aut)
	tests whether the automaton is deterministic More...
template<typename Tdc >
bool	is_sequential_tdc (const Tdc &tdc)
template<typename Aut >
bool	is_standard (const Aut &a)
template<typename Tdc >
bool	is_synchronizable (Tdc tdc)
template<typename Aut >
bool	is_synchronized_by (const Aut &aut, const typename labelset_t_of< Aut >::word_t &w)
template<typename Aut >
bool	is_synchronizing (const Aut &aut)
template<typename Aut >
bool	is_trim (const Aut &aut)
	Test whether the automaton is trim. More...
template<typename Aut >
bool	is_useless (const Aut &aut)
	Test whether the automaton has useful states. More...
template<typename Aut >
bool	is_valid (const Aut &aut)
	Tests if aut is valid. More...
template<typename RatExpSet >
bool	is_valid (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e)
b	join (const b &, const b &)
c	join (const b &, const c &)
maxmin	join (const b &, const maxmin &)
n	join (const b &, const n &)
noo	join (const b &, const noo &)
pmax	join (const b &, const pmax &)
q	join (const b &, const q &)
r	join (const b &, const r &)
z	join (const b &, const z &)
zmax	join (const b &, const zmax &)
zmin	join (const b &, const zmin &)
template<typename Context >
ratexpset< Context >	join (const b &a, const ratexpset< Context > &b)
c	join (const c &, const b &)
c	join (const c &, const c &)
c	join (const c &, const n &)
c	join (const c &, const q &)
c	join (const c &, const r &)
c	join (const c &, const z &)
template<typename LhsLabelSet , typename LhsWeightSet , typename RhsLabelSet , typename RhsWeightSet >
auto	join (const context< LhsLabelSet, LhsWeightSet > &a, const context< RhsLabelSet, RhsWeightSet > &b) -> context< join_t< LhsLabelSet, RhsLabelSet >, join_t< LhsWeightSet, RhsWeightSet >>
	The join of two contexts. More...
f2	join (const f2 &, const f2 &)
template<typename GenSet >
letterset< GenSet >	join (const letterset< GenSet > &lhs, const letterset< GenSet > &rhs)
	Compute the join with another labelset. More...
template<typename GenSet >
nullableset< letterset< GenSet > >	join (const letterset< GenSet > &lhs, const nullableset< letterset< GenSet >> &rhs)
template<typename GenSet1 , typename Ctx2 >
auto	join (const letterset< GenSet1 > &a, const ratexpset< Ctx2 > &b) -> ratexpset< context< join_t< letterset< GenSet1 >, labelset_t_of< Ctx2 >>, weightset_t_of< Ctx2 >>>
maxmin	join (const maxmin &, const b &)
maxmin	join (const maxmin &, const maxmin &)
n	join (const n &, const b &)
c	join (const n &, const c &)
n	join (const n &, const n &)
q	join (const n &, const q &)
r	join (const n &, const r &)
z	join (const n &, const z &)
template<unsigned K>
nn< K >	join (const nn< K > &, const nn< K > &)
noo	join (const noo &, const b &)
noo	join (const noo &, const noo &)
template<typename GenSet >
nullableset< letterset< GenSet > >	join (const nullableset< letterset< GenSet >> &lhs, const letterset< GenSet > &rhs)
template<typename GenSet >
nullableset< letterset< GenSet > >	join (const nullableset< letterset< GenSet >> &lhs, const nullableset< letterset< GenSet >> &rhs)
	compute the join with another labelset. More...
template<typename Lls , typename Rls >
auto	join (const nullableset< Lls > &lhs, const nullableset< Rls > &rhs) -> nullableset< decltype(join(*lhs.labelset(), *rhs.labelset()))>
oneset	join (const oneset &, const oneset &)
	The union of two labelsets. More...
pmax	join (const pmax &, const b &)
pmax	join (const pmax &, const pmax &)
template<typename PLS1 , typename PWS1 , typename PLS2 , typename PWS2 >
auto	join (const polynomialset< context< PLS1, PWS1 >> &p1, const polynomialset< context< PLS2, PWS2 >> &p2) -> polynomialset< context< join_t< PLS1, PLS2 >, join_t< PWS1, PWS2 >>>
template<typename PLS1 , typename PWS1 , typename WS2 >
auto	join (const polynomialset< context< PLS1, PWS1 >> &p1, const WS2 &w2) -> polynomialset< context< PLS1, join_t< PWS1, WS2 >>>
q	join (const q &, const b &)
c	join (const q &, const c &)
q	join (const q &, const n &)
q	join (const q &, const q &)
r	join (const q &, const r &)
q	join (const q &, const z &)
template<typename Context >
auto	join (const q &ws, const ratexpset< Context > &rs) -> join_t< ratexpset< Context >, q >
r	join (const r &, const b &)
c	join (const r &, const c &)
r	join (const r &, const n &)
r	join (const r &, const q &)
r	join (const r &, const r &)
r	join (const r &, const z &)
template<typename Context >
auto	join (const r &ws, const ratexpset< Context > &rs) -> join_t< ratexpset< Context >, r >
template<typename Context >
ratexpset< Context >	join (const ratexpset< Context > &a, const b &)
template<typename Context >
auto	join (const ratexpset< Context > &rs, const q &ws) -> ratexpset< context< labelset_t_of< Context >, join_t< weightset_t_of< Context >, q >>>
template<typename Context >
auto	join (const ratexpset< Context > &rs, const r &ws) -> ratexpset< context< labelset_t_of< Context >, join_t< weightset_t_of< Context >, r >>>
template<typename Context >
auto	join (const ratexpset< Context > &rs, const z &ws) -> ratexpset< context< labelset_t_of< Context >, join_t< weightset_t_of< Context >, z >>>
template<typename Ctx1 , typename GenSet2 >
auto	join (const ratexpset< Ctx1 > &a, const letterset< GenSet2 > &b) -> decltype(join(b, a))
template<typename Ctx1 , typename Ctx2 >
auto	join (const ratexpset< Ctx1 > &a, const ratexpset< Ctx2 > &b) -> ratexpset< join_t< Ctx1, Ctx2 >>
	The union of two ratexpsets. More...
template<typename T , typename U >
T	join (const T &l, const U &)
template<typename ValueSet >
auto	join (const ValueSet &vs) -> ValueSet
	The join of a single valueset. More...
template<typename ValueSet1 , typename ValueSet2 , typename ValueSet3 , typename... VSs>
auto	join (const ValueSet1 &vs1, const ValueSet2 &vs2, const ValueSet3 &vs3, const VSs &... vs) -> decltype(join(join(vs1, vs2), vs3, vs...))
template<typename GenSet >
wordset< GenSet >	join (const wordset< GenSet > &lhs, const wordset< GenSet > &rhs)
	Compute the union with another alphabet. More...
template<typename WS1 , typename PLS2 , typename PWS2 >
auto	join (const WS1 &w1, const polynomialset< context< PLS2, PWS2 >> &p2) -> polynomialset< context< PLS2, join_t< WS1, PWS2 >>>
z	join (const z &, const b &)
c	join (const z &, const c &)
z	join (const z &, const n &)
q	join (const z &, const q &)
r	join (const z &, const r &)
z	join (const z &, const z &)
template<typename Context >
auto	join (const z &ws, const ratexpset< Context > &rs) -> join_t< ratexpset< Context >, z >
zmax	join (const zmax &, const b &)
zmax	join (const zmax &, const zmax &)
zmin	join (const zmin &, const b &)
zmin	join (const zmin &, const zmin &)
template<unsigned N>
zz< N >	join (const zz< N > &, const zz< N > &)
template<typename... Auts>
auto	join_automata (Auts &&... auts) -> decltype(make_mutable_automaton(join(auts->context()...)))
	Join between automata. More...
template<typename Aut >
void	js_add_metadata (Aut &aut, json::object_t *p)
template<typename Context >
mutable_automaton< Context >	js_parse_aut_content (const Context &context, json::object_t const *p)
template<typename RatExpSet >
RatExpSet::ratexp_t	js_parse_exp_content (const RatExpSet &rs, json::node_t const *p)
template<typename Automaton , unsigned version = version::fsm_json>
std::ostream &	js_print (Automaton aut, std::ostream &o, bool full=false, json_ast_t extra_metadata=json_ast::empty())
template<typename RatExpSet , unsigned version = version::fsm_json>
std::ostream &	js_print (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e, std::ostream &o, json_ast_t extra_metadata=json_ast::empty())
template<unsigned version = version::fsm_json>
json::object_t *	json_creator ()
template<unsigned version = version::fsm_json>
json::object_t *	json_format ()
template<unsigned version = version::fsm_json>
json::object_t *	json_timestamp ()
template<typename... Auts>
auto	k_product_no_history (const Auts &... as) -> decltype(join_automata(as...))
	Build the (accessible part of the) product. More...
template<typename... Auts>
auto	k_product_with_history (const Auts &... as) -> decltype(join_automata(as...))
	Build the (accessible part of the) product. More...
template<typename... Auts>
auto	k_shuffle_no_history (const Auts &... as) -> decltype(join_automata(as...))
	Build the (accessible part of the) product. More...
template<typename... Auts>
auto	k_shuffle_with_history (const Auts &... as) -> decltype(join_automata(as...))
	Build the (accessible part of the) product. More...
template<typename LabelSet >
bool	label_is_zero (const LabelSet &,...) ATTRIBUTE_CONST
template<typename LabelSet >
auto	label_is_zero (const LabelSet &ls, const typename LabelSet::value_t *l) -> decltype(ls.is_zero(l), bool())
template<class Context >
mutable_automaton< Context >	ladybird (const Context &ctx, unsigned n)
	Returns a "ladybird" automaton with n states. More...
template<typename Aut >
Aut::element_type::automaton_nocv_t	left_mult (const Aut &aut, const weight_t_of< Aut > &w, bool standard=false)
template<typename RatExpSet >
RatExpSet::ratexp_t	left_mult (const RatExpSet &rs, const weight_t_of< RatExpSet > &w, const typename RatExpSet::value_t &r)
template<typename Aut >
Aut &	left_mult_here (Aut &res, const weight_t_of< Aut > &w, bool standard=false)
	multiplies the initial states by a weight More...
template<typename Aut >
Aut	left_reduce (const Aut &input)
template<class RatExpSet >
RatExpSet::ratexp_t	less_than (const RatExpSet &rs, const typename RatExpSet::ratexp_t &v)
template<typename Aut >
auto	letterize (const Aut &aut, bool keep_history=true) -> typename internal::letterizer< Aut, labelset_t_of< Aut >>::ret_automaton_t
template<unsigned I, typename Tdc >
auto	letterize_tape (const Tdc &tdc, bool keep_history=true) -> typename internal::tdc_letterizer< Tdc, I, typename labelset_t_of< Tdc >::template valueset_t< I >>::ret_transducer_t
template<typename Aut >
internal::lifted_automaton_t< Aut >	lift (const Aut &a, bool keep_history=true)
	Lift labels to weights. More...
template<typename RatExpSet >
internal::lifted_ratexpset_t< RatExpSet >::ratexp_t	lift (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e)
template<typename Tdc >
auto	lift_tdc (const Tdc &tdc, bool keep_history=true) -> typename internal::tdc_lifter< Tdc >::automaton_t
template<typename T >
mutable_automaton< context< ctx::lal_char, T > >	load_automaton (std::istream &is)
template<typename T >
mutable_automaton< context< ctx::lan_char, T > >	load_automaton_with_epsilon (std::istream &is)
template<typename T >
mutable_automaton< context< ctx::lal_char, T > >	make_automaton (const std::set< char > &letters)
	Build an awali weighted automaton labeled by letters. More...
template<typename T >
mutable_automaton< context< ctx::lan_char, T > >	make_automaton_with_epsilon (const std::set< char > &letters)
	Build an awali weighted automaton labeled by letters with epsilon transitions. More...
template<typename T >
context< ctx::lal_char, T >	make_context (const std::set< char > &letters)
template<typename Context >
mutable_automaton< Context >	make_mutable_automaton (const Context &ctx)
template<typename T >
std::pair< T, T >	make_ordered_pair (T e1, T e2)
template<typename RATEXPSET >
auto	make_ratexp (RATEXPSET &ratset, const std::string &exp) -> typename RATEXPSET::ratexp_t
template<typename T >
ratexpset_of< context< ctx::lal_char, T > >	make_ratexpset ()
template<typename SharedPtr , typename... Args>
SharedPtr	make_shared_ptr (Args &&... args)
	Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type. More...
template<typename T >
ratexpset_of< context< ctx::lat< ctx::lan_char, ctx::lan_char >, T > >	make_tdc_ratexpset ()
template<typename T >
mutable_automaton< context< ctx::lat< ctx::lan_char, ctx::lan_char >, T > >	make_transducer (const std::set< char > &letterA, const std::set< char > &letterB)
template<typename... Auts>
auto	make_tuple_automaton (const Auts &... auts) -> tuple_automaton< Auts... >
template<typename... Valuesets>
auto	make_tupleset (std::tuple< Valuesets... > t) -> tupleset< Valuesets... >
template<typename LhsLabelSet , typename LhsWeightSet , typename RhsLabelSet , typename RhsWeightSet >
auto	meet (const context< LhsLabelSet, LhsWeightSet > &a, const context< RhsLabelSet, RhsWeightSet > &b) -> context< meet_t< LhsLabelSet, RhsLabelSet >, join_t< LhsWeightSet, RhsWeightSet >>
	The meet of two contexts. More...
template<typename GenSet >
letterset< GenSet >	meet (const letterset< GenSet > &lhs, const letterset< GenSet > &rhs)
	Compute the meet with another labelset. More...
template<typename GenSet >
nullableset< letterset< GenSet > >	meet (const letterset< GenSet > &lhs, const nullableset< letterset< GenSet >> &rhs)
template<typename GenSet >
nullableset< letterset< GenSet > >	meet (const nullableset< letterset< GenSet >> &lhs, const letterset< GenSet > &rhs)
template<typename GenSet >
nullableset< letterset< GenSet > >	meet (const nullableset< letterset< GenSet >> &lhs, const nullableset< letterset< GenSet >> &rhs)
	Compute the meet with another labelset. More...
template<typename Lls , typename Rls >
auto	meet (const nullableset< Lls > &lhs, const nullableset< Rls > &rhs) -> nullableset< decltype(meet(*lhs.labelset(), *rhs.labelset()))>
oneset	meet (const oneset &, const oneset &)
	The meet of two labelsets. More...
template<typename Ctx1 , typename Ctx2 >
auto	meet (const ratexpset< Ctx1 > &a, const ratexpset< Ctx2 > &b) -> ratexpset< meet_t< Ctx1, Ctx2 >>
	The meet of two ratexpsets. More...
template<typename ValueSet >
auto	meet (const ValueSet &vs) -> ValueSet
	The meet of a single valueset. More...
template<typename ValueSet1 , typename ValueSet2 , typename ValueSet3 , typename... VSs>
auto	meet (const ValueSet1 &vs1, const ValueSet2 &vs2, const ValueSet3 &vs3, const VSs &... vs) -> decltype(meet(meet(vs1, vs2), vs3, vs...))
template<typename GenSet >
wordset< GenSet >	meet (const wordset< GenSet > &lhs, const wordset< GenSet > &rhs)
	Compute the meet with another alphabet. More...
template<typename... Auts>
auto	meet_automata (Auts &&... auts) -> decltype(make_mutable_automaton(meet(auts->context()...)))
	Meet between automata. More...
template<typename Aut , typename StateList >
auto	merge (const Aut &a, std::vector< StateList > &classes, bool keep_history=true) -> Aut
template<typename Aut >
Aut	min_quotient (const Aut &aut, quotient_algo_t algo=MOORE, bool keep_history=true)
template<typename Aut >
Aut	min_quotient_det (const Aut &aut, quotient_algo_t algo=MOORE, bool keep_history=true)
template<typename Aut >
Aut	minimize (const Aut &aut, quotient_algo_t algo=MOORE, bool keep_history=true)
template<typename Aut >
Aut::element_type::automaton_nocv_t	minimize_brzozowski (const Aut &a)
template<typename Aut >
void	moore_det (const Aut &aut, std::vector< std::vector< state_t > > &states_in_part)
	Moore algorithm for the minimization of deterministic Boolean automata (DFA), not necessarily complete. More...
template<typename Aut >
unsigned	moore_quotient (const Aut &aut, std::vector< std::vector< state_t > > &states_in_part)
template<typename Context >
mutable_automaton< Context >	n_ultimate (const Context &ctx, typename Context::labelset_t::value_t a, unsigned n)
	Returns an automaton which recognizes words with a specific n-ultimate letter. More...
template<typename Aut >
transition_t	new_epsilon_trans (Aut a, state_t src, state_t dst, weight_t_of< Aut > w)
	Helper to create a new epsilon transition. More...
template<typename Aut >
transition_t	new_epsilon_trans (const Aut a, state_t src, state_t dst)
	Helper to create a new epsilon transition. More...
template<typename Aut >
state_t	next_heuristic (const Aut &a)
template<typename Aut >
state_t	next_in_order (const Aut &a)
template<typename Aut >
size_t	num_accessible_states (const Aut &aut)
	Number of accessible states. More...
template<typename Aut >
size_t	num_coaccessible_states (const Aut &aut)
	Number of coaccessible states. More...
template<typename Aut >
size_t	num_useful_states (const Aut &aut)
	Number of useful states. More...
std::shared_ptr< std::istream >	open_input_file (const std::string &file)
	Open file for reading and return its autoclosing stream. More...
std::shared_ptr< std::ostream >	open_output_file (const std::string &file)
	Open file for writing and return its autoclosing stream. More...
bool	operator!= (empty_t, empty_t)
empty_t &	operator-- (empty_t &e)
bool	operator< (empty_t, empty_t)
bool	operator<= (empty_t, empty_t)
bool	operator== (empty_t, empty_t)
bool	operator> (empty_t, empty_t)
bool	operator>= (empty_t, empty_t)
template<size_t I, typename Aut >
Aut	outsplit (const Aut &aut, bool keep_history=true)
template<size_t I, typename Aut >
std::enable_if<!internal::select_one< labelset_t_of< Aut >, I >::has_one(), void >::type	outsplit_here (Aut &)
template<size_t I, typename Aut >
std::enable_if< internal::select_one< labelset_t_of< Aut >, I >::has_one(), void >::type	outsplit_here (Aut &aut)
template<typename Aut >
pair_automaton< Aut >	pair (const Aut &aut, bool keep_initials=false)
template<typename RatExpSet >
RatExpSet::ratexp_t	parse_exp (const RatExpSet &ratexpset, const std::string &s, bool check_complete=true, bool strict_alphabet=true)
	parser of rational expressions More...
template<size_t I, typename Aut >
auto	partial_identity (const Aut &in, bool keep_history=true) -> typename internal::partial_identiter< Aut, I >::out_automaton_t
	Builds a transducer realizing the identity on a language. More...
template<typename Aut >
std::vector< transition_t >	path_bfs (const Aut &aut, state_t start, state_t end)
template<typename Aut >
std::unordered_map< state_t, std::pair< unsigned, transition_t > >	paths_ibfs (const Aut &aut, std::vector< state_t > start)
template<typename Aut >
auto	power (const Aut &aut, unsigned n) -> typename Aut::element_type::automaton_nocv_t
template<typename Aut >
Aut::element_type::automaton_nocv_t	prefix (const Aut &a, bool keep_history=true)
template<typename Aut >
void	prefix_here (Aut &a)
	Make all coaccessible states final. More...
template<typename RatExpSet >
std::ostream &	print (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e, std::ostream &o, bool with_dot=false)
template<typename Lhs , typename Rhs >
auto	product (const Lhs &lhs, const Rhs &rhs, bool keep_history=true) -> decltype(join_automata(lhs, rhs))
template<size_t I, typename Tdc >
auto	projection (const Tdc &in, bool keep_history=true) -> typename internal::projector< Tdc, I >::out_automaton_t
	Projection of one tape of a transducer. More...
template<size_t... I, typename Tdc >
auto	projections (const Tdc &in, bool keep_history=true) -> typename internal::projectors< Tdc, I... >::out_automaton_t
	Projection and/or permutation of tapes of a transducer. More...
template<typename OutWeightSet , typename RatExpSet >
auto	promote_ratexpset (const RatExpSet &ratexpset, const OutWeightSet &out_weightset=OutWeightSet()) -> typename rat::expcopy_visitor< RatExpSet, OutWeightSet >::out_ratexpset_t
	Compute a derived ratexpset. More...
template<typename Aut >
auto	proper (const Aut &aut, direction_t dir=BACKWARD, bool prune=true, bool keep_history=true) -> decltype(copy(aut))
	Eliminate spontaneous transitions. More...
template<typename Aut >
void	proper_here (Aut &aut, direction_t dir=BACKWARD, bool prune=true)
	Eliminate spontaneous transitions in place. More...
template<typename... Args>
ATTRIBUTE_NORETURN void	raise (Args &&... args)
	Raise a runtime_error with the concatenation of args as message. More...
template<typename RatExpSet >
auto	ratexp_copy (const typename RatExpSet::ratexp_t &exp, const RatExpSet &ratexpset) -> typename rat::expcopy_visitor< RatExpSet >::out_ratexp_t
	copy a rational expression More...
template<typename OutWeightSet , typename RatExpSet >
auto	ratexp_copy (const typename RatExpSet::ratexp_t &exp, const RatExpSet &ratexpset, const OutWeightSet &out_weightset=OutWeightSet()) -> typename rat::expcopy_visitor< RatExpSet, OutWeightSet >::out_ratexp_t
	copy a rational expression More...
template<typename RatExpSet >
auto	ratexp_support (const typename RatExpSet::ratexp_t &exp, const RatExpSet &ratexpset) -> typename rat::expsupport_visitor< RatExpSet >::out_ratexp_t
	support of a rational expression More...
template<typename RatExpSet , unsigned version = version::fsm_json>
json_ast_t	ratexp_to_ast (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e, json_ast_t extra_metadata=json_ast::empty())
template<typename Context >
auto	read_label (std::istream &is, const Context &ctx) -> label_t_of< Context >
template<typename Context >
auto	read_polynomial (const Context &ctx, std::istream &is) -> typename polynomialset< Context >::value_t
template<typename Context >
auto	read_weight (const Context &ctx, std::istream &is) -> weight_t_of< Context >
template<typename Tdc >
auto	realtime (const Tdc &tdc, bool keep_history=true) -> typename internal::realtimer< Tdc >::automaton_t
template<typename Aut >
Aut	reduce (const Aut &input)
template<typename Aut >
void	remove_letters (Aut &aut, const std::set< typename labelset_t_of< Aut >::letter_t > &letters, bool del_unvalid_transitions=true)
	Remove letters from the alphabet of the automaton. More...
template<typename... Args>
void	require (bool b, Args &&... args)
	If b is not verified, raise an error with args as message. More...
template<typename Aut >
std::stack< state_t >	reverse_postorder (const Aut &aut)
	Get all vertices in reverse postorder. More...
template<typename Aut >
Aut::element_type::automaton_nocv_t	right_mult (const Aut &aut, const weight_t_of< Aut > &w)
template<typename RatExpSet >
RatExpSet::ratexp_t	right_mult (const RatExpSet &rs, const typename RatExpSet::value_t &r, const weight_t_of< RatExpSet > &w)
template<typename Aut >
Aut &	right_mult_here (Aut &res, const weight_t_of< Aut > &w)
template<typename Aut >
std::pair< std::unordered_map< state_t, unsigned int >, std::vector< std::vector< state_t > > >	scc_iterative (Aut aut)
	Iterative computation of strongly connected components. More...
template<typename Aut >
std::vector< state_t >	scc_of (Aut aut, state_t s)
	Computes the strongly connected component of a state. More...
template<typename Aut >
std::pair< std::unordered_map< state_t, unsigned int >, std::vector< std::vector< state_t > > >	scc_recursive (Aut aut)
	Recursive computation of strongly connected components. More...
template<typename Aut >
transition_t	set_epsilon_trans (Aut a, state_t src, state_t dst, weight_t_of< Aut > w)
	Helper to set an epsilon transition. More...
template<typename Aut >
transition_t	set_epsilon_trans (const Aut a, state_t src, state_t dst)
	Helper to set an epsilon transition. More...
template<typename Automaton >
internal::enumerater< Automaton >::polynomial_t	shortest (const Automaton &aut, unsigned num)
	Computes the weight of the num smallest words accepted by the automaton. More...
template<typename Lhs , typename Rhs >
auto	shuffle (const Lhs &lhs, const Rhs &rhs, bool keep_history=true) -> decltype(join_automata(lhs, rhs))
template<typename Aut , typename Compare >
void	sort (Aut a, Compare p)
template<size_t I, typename Tdc >
void	sort_tape (Tdc t)
template<typename RatExpSet >
rat::ratexp_polynomial_t< RatExpSet >	split (const RatExpSet &rs, const rat::ratexp_polynomial_t< RatExpSet > &p)
	Split a polynomial of ratexps. More...
template<typename RatExpSet >
rat::ratexp_polynomial_t< RatExpSet >	split (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e)
	Split a ratexp. More...
template<typename Aut >
Aut	standard (Aut &aut, bool keep_history=true)
template<typename Aut , typename Context = context_t_of<Aut>>
Aut	standard (const Context &ctx, const typename Context::ratexp_t &e)
template<typename RatExpSet >
mutable_automaton< typename RatExpSet::context_t >	standard (const RatExpSet &rs, const typename RatExpSet::ratexp_t &e)
template<typename Aut >
void	standard_here (Aut &aut)
	Turn aut into a standard automaton. More...
template<typename Aut >
Aut::element_type::automaton_nocv_t	star (const Aut &aut)
	Star of an automaton. More...
template<typename RatExpSet >
unsigned	star_height (const typename RatExpSet::ratexp_t &e)
	Star height of a ratexp. More...
template<typename Aut >
Aut &	star_here (Aut &res)
template<typename RatExpSet >
RatExpSet::value_t	star_normal_form (const RatExpSet &rs, const typename RatExpSet::value_t &e)
	Star_Normal_Forming a typed ratexp shared_ptr. More...
std::string	str_escape (const int c)
std::string	str_escape (const std::string &s)
std::ostream &	str_escape (std::ostream &os, const int c)
std::ostream &	str_escape (std::ostream &os, const std::string &str)
template<typename Aut >
void	sub_automaton (Aut &aut, const std::set< state_t > &sts)
template<typename Aut , typename Pred >
void	sub_automaton (Aut &aut, Pred keep_state)
template<typename Aut >
Aut::element_type::automaton_nocv_t	suffix (const Aut &a, bool keep_history=true)
template<typename Aut >
void	suffix_here (Aut &a)
	Make all accessible states initial. More...
template<typename Aut1 , typename Aut2 >
auto	sum (const Aut1 &aut1, const Aut2 &aut2, bool sum_standard=false) -> decltype(join_automata(aut1, aut2))
	sums two automata More...
template<typename ValueSet >
ValueSet::value_t	sum (const ValueSet &vs, const typename ValueSet::value_t &lhs, const typename ValueSet::value_t &rhs)
	Sums of values. More...
template<typename Res , typename Aut >
Res &	sum_here (Res &res, const Aut &aut, bool sum_standard=false)
	Merge transitions of b into those of res. More...
template<typename RatExpSet >
auto	support_ratexpset (const RatExpSet &ratexpset) -> typename rat::expsupport_visitor< RatExpSet >::out_ratexpset_t
	Compute a derived ratexpset. More...
template<typename Tdc >
Tdc	synchronize (const Tdc &tdc, bool keep_history=true)
template<typename Aut >
labelset_t_of< Aut >::word_t	synchronizing_word (const Aut &aut, const std::string &algo="greedy")
template<typename Aut , typename Context = context_t_of<Aut>>
Aut	thompson (const Context &ctx, const typename Context::ratexp_t &exp, bool keep_history=true)
	builds a Thompson automaton More...
template<typename RatExpSet >
mutable_automaton< sttc::nullable_of< typename RatExpSet::context_t > >	thompson (const RatExpSet &rs, const typename RatExpSet::ratexp_t &exp, bool keep_history=true)
	builds a Thompson automaton More...
template<typename AutPtr >
std::ostream &	tikz (const AutPtr &aut, std::ostream &out)
	Format automaton to TikZ format. More...
template<typename Aut >
auto	to_lal (const Aut &aut, direction_t dir=BACKWARD, bool prune=true, bool keep_history=true) -> typename internal::dispatch_lal_lan< Aut, labelset_t_of< Aut >>::l_automaton_t
template<typename Aut >
auto	to_lan (const Aut &aut, bool keep_history=true) -> typename internal::dispatch_lal_lan< Aut, labelset_t_of< Aut >>::n_automaton_t
template<typename Aut , typename AutOut = typename Aut::element_type::automaton_nocv_t>
AutOut	transpose (Aut &aut, bool keep_history=true)
template<class RatExpSet >
RatExpSet::ratexp_t	transpose (const RatExpSet &rs, const typename RatExpSet::ratexp_t &v)
template<typename Aut >
void	transpose_here (Aut &aut)
template<typename Aut >
std::shared_ptr< internal::transpose_view_impl< Aut > >	transpose_view (std::shared_ptr< Aut > aut)
template<typename Aut >
Aut::element_type::automaton_nocv_t	trim (const Aut &aut, bool keep_history=true)
	Trim subautomaton. More...
template<typename Aut >
void	trim_here (Aut &aut)
	In-place trim subautomaton. More...
template<class Aut >
Aut	universal (const Aut &a)
template<typename Aut >
std::set< state_t >	useful_states (const Aut &aut, bool include_pre_post=false)
	List of useful states. More...
	VAUCR_WEIGHTS_BINARY (b, z, z)
	VAUCR_WEIGHTS_BINARY (z, b, z)
	VAUCR_WEIGHTS_BINARY (z, z, z)
template<typename Aut >
auto	weighted_determinize (const Aut &aut) -> mutable_automaton< context_t_of< Aut >>
	Weighted determinization of the automaton. More...
template<typename Aut , typename Context = context_t_of<Aut>>
Aut	weighted_thompson (const Context &ctx, const typename Context::ratexp_t &exp, bool keep_history=true)
	builds a variant of the Thompson automaton without epsilon cycles More...
template<typename RatExpSet >
mutable_automaton< sttc::nullable_of< typename RatExpSet::context_t > >	weighted_thompson (const RatExpSet &rs, const typename RatExpSet::ratexp_t &exp, bool keep_history=true)
	builds a variant of the Thompson automaton without epsilon cycles More...
template<typename Context >
mutable_automaton< Context >	witness (const Context &ctx, unsigned n)
	Returns an automaton with n states. More...

Detailed Description

Namespace for the static layer of Awali.

Automata, rational expressions and algorithms are templated with the context.

---

Data Structure Documentation

awali::sttc::empty_t

struct awali::sttc::empty_t

Empty labels, for LAO.

awali::sttc::exp_stats_t

struct awali::sttc::exp_stats_t

gathers informations on some rational expression

This structure is returned by the function exp_stats

Data Fields
unsigned	height
unsigned	length
unsigned	size
unsigned	star_height

Typedef Documentation

context_t_of

template<typename ValueSet >

using awali::sttc::context_t_of = typedef typename internal:: context_t_of_impl<internal::base_t<ValueSet> >::type

Helper to retrieve the type of the context of a value set.

For instance, if ValueSet is an a type of automaton, context_t_of<ValueSet> is the type of its context.

Template Parameters

ValueSet

the type of the value set.

join_t

template<typename... ValueSets>

using awali::sttc::join_t = typedef decltype(join(std::declval<ValueSets>()...))

Computation of the join of some value sets.

The join of two value sets is the most restrictive value set which is an extension of both ones.

For instance, the join of the weightset z and the weightset ratexpset<context_t<lal_char,b>> is the weightset ratexpset<context_t<lal_char,z>>

Template Parameters

ValueSets

a list of value sets

label_t_of

template<typename ValueSet >

using awali::sttc::label_t_of = typedef typename internal:: label_t_of_impl<internal::base_t<ValueSet> >::type

Helper to retrieve the type of the labels of a value set.

See context_t_of

Template Parameters

ValueSet

the type of the value set.

labelset_t_of

template<typename ValueSet >

using awali::sttc::labelset_t_of = typedef typename internal:: labelset_t_of_impl<internal::base_t<ValueSet> >::type

Helper to retrieve the type of the labelset of a value set.

See context_t_of

Template Parameters

ValueSet

the type of the value set.

labelset_types

template<typename... ValueSets>

using awali::sttc::labelset_types = typedef internal::labelset_types<void, ValueSets...>

meet_t

template<typename... ValueSets>

using awali::sttc::meet_t = typedef decltype(meet(std::declval<ValueSets>()...))

Computation of the meet of some value sets.

The meet of two value sets is the lees restrictive value set whose both ones are extensions.

Template Parameters

ValueSets

a list of value sets

mutable_automaton

template<typename Context >

using awali::sttc::mutable_automaton = typedef std::shared_ptr<internal::mutable_automaton_impl<Context> >

not_nullable_of

template<typename Context >

using awali::sttc::not_nullable_of = typedef context<typename labelset_trait<typename Context::labelset_t>::not_nullable_t, typename Context::weightset_t>

nullable_of

template<typename Context >

using awali::sttc::nullable_of = typedef context<typename labelset_trait<typename Context::labelset_t>::nullable_t, typename Context::weightset_t>

pair_automaton

template<typename Aut >

using awali::sttc::pair_automaton = typedef std::shared_ptr<internal::pair_automaton_impl<Aut> >

partition_automaton

template<typename Aut >

using awali::sttc::partition_automaton = typedef std::shared_ptr<internal::partition_automaton_impl<Aut> >

A subset automaton as a shared pointer.

permutation_automaton

template<typename Aut >

using awali::sttc::permutation_automaton = typedef std::shared_ptr<internal::permutation_automaton_impl<Aut> >

A permutation automaton as a shared pointer.

ratexp_automaton

template<typename Aut >

using awali::sttc::ratexp_automaton = typedef std::shared_ptr<internal::ratexp_automaton_impl<Aut> >

A ratexp automaton as a shared pointer.

ratexp_context_of

template<typename Context >

using awali::sttc::ratexp_context_of = typedef context< typename labelset_trait<typename Context::labelset_t>::ratlabelset_t, typename Context::weightset_t >

ratexpset

template<typename Context >

using awali::sttc::ratexpset = typedef variadic_mul_mixin<rat::ratexpset_impl<Context> >

ratexpset_of

template<typename Context >

using awali::sttc::ratexpset_of = typedef ratexpset<ratexp_context_of<Context> >

state_chooser_t

template<typename Aut , typename Lifted = internal::lifted_automaton_t<Aut>>

using awali::sttc::state_chooser_t = typedef std::function<state_t(const Lifted&)>

A state (inner) from an automaton.

tuple_automaton

template<typename... Auts>

using awali::sttc::tuple_automaton = typedef std::shared_ptr<internal::tuple_automaton_impl<Auts...> >

A product automaton as a shared pointer.

weight_t_of

template<typename ValueSet >

using awali::sttc::weight_t_of = typedef typename internal:: weight_t_of_impl<internal::base_t<ValueSet> >::type

Helper to retrieve the type of the weights of a value set.

See context_t_of

Template Parameters

ValueSet

the type of the value set.

weightset_t_of

template<typename ValueSet >

using awali::sttc::weightset_t_of = typedef typename internal:: weightset_t_of_impl<internal::base_t<ValueSet> >::type

Helper to retrieve the type of the weightset of a value set.

See context_t_of

Template Parameters

ValueSet

the type of the value set.

Function Documentation

accessible()

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::accessible	(	const Aut &	aut,
		bool	keep_history = true
	)

Accessible subautomaton.

Computes a fresh automaton with a copy of the accessible part of aut. If the keep_history flag is true, the result is endowed with a SINGLE history.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)
keep_history	A Boolean that tells whether the history must be registered.

Returns

A mutable Awali automaton

accessible_here()

template<typename Aut >

void awali::sttc::accessible_here

(

Aut &

aut

)

In-place accessible subautomaton.

Remove every non accessible state of aut.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static mutable Awali automaton

accessible_states()

template<typename Aut >

std::set<state_t> awali::sttc::accessible_states	(	const Aut &	aut,
		bool	include_pre_post = false
	)

List of accessible states.

Computes the list of accessible states in aut.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)
include_pre_post	if true, the pre-initial and the post-final states may be added to the result.

Returns

a standard set

add_epsilon_trans() [1/2]

template<typename Aut >

weight_t_of<Aut> awali::sttc::add_epsilon_trans	(	Aut	a,
		state_t	src,
		state_t	dst,
		weight_t_of< Aut >	w
	)

Helper to add an epsilon transition.

Like the add_transition method of automata, this function either create an epsilon transition or add the weight to an existing epsilon-transition with the same ends.

Template Parameters

Aut	the type of the automaton

Parameters

a	the automaton
src	the source state of the transition
dst	the destination state of the transition
w	the weight of the transition

Returns

the resulting weight of the transition

Exceptions

runtime_error

if the automaton does not admit epsilon transitions

add_epsilon_trans() [2/2]

template<typename Aut >

weight_t_of<Aut> awali::sttc::add_epsilon_trans	(	const Aut	a,
		state_t	src,
		state_t	dst
	)

Helper to add an epsilon transition.

Like the add_transition method of automata, this function either create an epsilon transition or add the weight to an existing epsilon-transition with the same ends.

Template Parameters

Aut	the type of the automaton

Parameters

a	the automaton
src	the source state of the transition
dst	the destination state of the transition

Returns

the resulting weight of the transition

Exceptions

runtime_error

if the automaton does not admit epsilon transitions

add_path() [1/2]

template<typename Aut >

void awali::sttc::add_path	(	Aut &	aut,
		state_t	p,
		state_t	q,
		const std::string &	s,
		bool	strict_alphabet = true
	)

adds a subautomaton realizing the series s between states p and q of aut.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the automaton in which the subautomaton is inserted
p	the source state
q	the destination state
s	the inserted series
strict_alphabet	if true, the letters in the expression must belong to the alphabet of the automaton; otherwise, they can be added to the alphabet

Exceptions

std::runtime_error	if aut does not allow epsilon-transitions and s is not proper
parse_exception	if the expression is malformed
domain_error	if strict_alphabet is true and a letter does not belong to the alphabet

The string s is parsed to obtain a rational expression; the function add_path is then called

add_path() [2/2]

template<typename Aut >

auto awali::sttc::add_path	(	Aut &	aut,
		state_t	p,
		state_t	q,
		const typename context_t_of< Aut >::ratexp_t &	exp
	)		-> typename std::enable_if<!labelset_t_of<Aut>::has_one(),void>::type

adds a subautomaton realizing the series exp between states p and q of aut.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the automaton in which the subautomaton is inserted
p	the source state
q	the destination state
exp	the inserted series

Exceptions

std::runtime_error

if aut does not allow epsilon-transitions and exp is not proper

The behaviour of the function depends whether the automaton aut allows epsilon-transitions.

– If it does, a compact_thompson automaton is built from exp and copied between states p and q.

– If it does not, a standard automaton is built from exp and copied between states p and q. In this case, the series exp must be proper.

allow_words()

template<typename Aut >

auto awali::sttc::allow_words	(	const Aut &	aut,
		bool	keep_history = true
	)		-> typename internal::allowworder<Aut>::ret_automaton_t

Turns the automaton into an automaton labeled with words.

If the input automaton already accepts words as labels, a copy is returned.

Template Parameters

Aut	the type of the input automaton

Parameters

aut	the input automaton
keep_history	if true the result is endowed with a single_history to the input automaton

Returns

an automaton where labels are words

are_equivalent()

template<typename Aut0 , typename Aut2 >

bool awali::sttc::are_equivalent	(	const Aut0 &	aut1,
		const Aut2 &	aut2
	)

Tests if aut1 and aut2 are equivalent.

Parameters

aut1
aut2

Returns

true if aut1 and aut2 associates every word with the same weight.

Precondition

The algorithm only work if either:

• both aut1 and aut2 are over weightset B;
• automaton aut2 is over a weightset that is a field, or over Z, and the context of aut1 is compatible with the context of aut2.

are_isomorphic()

template<typename Aut1 , typename Aut2 >

bool awali::sttc::are_isomorphic	(	const Aut1 &	a1,
		const Aut2 &	a2
	)

tests whether two automata are isomorphic

Template Parameters

Aut1	the type of the first automaton
Aut2	the type of the second automaton

Parameters

a1	the first automaton
a2	the second automaton

Returns

true if and only if the automata are isomorphic

aut_to_ast()

template<typename Automaton , unsigned version = version::fsm_json>

json_ast_t awali::sttc::aut_to_ast	(	Automaton	aut,
		json_ast_t	extra_metadata = json_ast::empty(),
		bool	full = false
	)

aut_to_exp() [1/2]

template<typename Aut , typename Context = ratexpset_of<context_t_of<Aut>>>

Context::ratexp_t awali::sttc::aut_to_exp

(

const Aut &

a

)

Default state elimination algorithm.

Based on aut_to_exp. In this algorithm, every state has a rank which is the product of the number of its incoming transitions (except loops) by its outgoing transitions (except loops)

The set of remaining states is (partially) ordered : a state s is smaller than a state t if :

• the rank of s is smaller than the rank of t;
• or they have the same rank, s has no loop and t has.
  

The states are processed with respect to this ordering (the rank may evolve during the algorithm)

Template Parameters

Aut	the type of the automaton
Context	the context of rational expressions

Parameters

a	the automaton

Returns

a rational expression describing the behaviour of the automaton

aut_to_exp() [2/2]

template<typename Aut , typename Context = ratexpset_of<context_t_of<Aut>>>

Context::ratexp_t awali::sttc::aut_to_exp	(	const Aut &	a,
		const state_chooser_t< Aut > &	next_state
	)

Generic state elimination algorithm.

The automaton is first converted into an automaton where the labels are lifted to weights as rational expressions. Then the algorithm iterates over states. For every state, for every pair formed by an incoming transition t and an outgoing one t', a transition is added from the source of t to the destination of t'. When every pair has been processed, the state is deleted.

Template Parameters

Aut	the type of the automaton
Context	the context of rational expressions

Parameters

a	the automaton
next_state	an iterator on states which determines the elimination ordering

Returns

a rational expression describing the behaviour of the automaton

aut_to_exp_in_order()

template<typename Aut , typename Context = ratexpset_of<context_t_of<Aut>>>

Context::ratexp_t awali::sttc::aut_to_exp_in_order

(

const Aut &

a

)

Basic state elimination algorithm.

Based on aut_to_exp.
In this algorithm, the state are processed with respect to their index, which generally corresponds to the order of creation.

Template Parameters

Aut	the type of the automaton
Context	the context of rational expressions

Parameters

a	the automaton

Returns

a rational expression describing the behaviour of the automaton

bracketed()

std::string awali::sttc::bracketed	(	std::istream &	i,
		const char	lbracket,
		const char	rbracket
	)

An narrow-char stream that discards the output.

An wide-char stream that discards the output. Extract the string which is here between lbracket and rbracket. Support nested lbracket/rbracket.

cerny()

template<typename Ctx >

mutable_automaton<Ctx> awali::sttc::cerny	(	const Ctx &	ctx,
		unsigned	num_states
	)

Cerny automata are automata whose synchronizing word length is always (n - 1)^2, the upper bound of the Cerny's conjecture.

Their transition function d(q, l) is defined by:

• (q + 1) % n if l == a
• q if l != a and q != n - 1
• 0 if l != a and q == n - 1

chain() [1/2]

template<typename Aut >

Aut awali::sttc::chain	(	const Aut &	aut,
		unsigned	min,
		int	max
	)

chains automata to compute powers of a series

If s is the series realized by aut, the series realized by the computed automaton is

• the sum of powers of s from min to max if min≤max
  
• the sum of powers of s from min to infinity if max is negative
  
• s to the power min otherwise

Template Parameters

Aut	the type of the automaton

Parameters

aut	the automaton
min	a non negative integer
max	an integer

Returns

an automaton

chain() [2/2]

template<typename RatExpSet >

RatExpSet::ratexp_t awali::sttc::chain	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	r,
		unsigned	min,
		int	max
	)

computes powers of rational exp

the result is

• the sum of powers of r from min to max if min≤max
  
• the sum of powers of r from min to infinity if max is negative
  
• r to the power min otherwise

Template Parameters

RatExpSet

type of the value set of the expression

Parameters

rs	the value set of the expression
r	a rational expression
min	a non negative integer
max	an integer

Returns

a rational expression

change_alphabet()

template<typename Aut >

void awali::sttc::change_alphabet	(	Aut &	aut,
		const std::set< typename labelset_t_of< Aut >::letter_t > &	letters,
		bool	del_unvalid_transitions = true
	)

Change letters in the alphabet of the automaton.

This function replaces the context of the automaton by a new context where the alphabet is given by the specified letters

Template Parameters

Aut	the type of the automaton
Letter	the type of the letters

Parameters

aut	the automaton
letters	a set of letters
del_unvalid_transitions	if true, the transitions which carry a label that is not valid w.r.t the new alphabet are deleted

coaccessible()

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::coaccessible	(	const Aut &	aut,
		bool	keep_history = true
	)

Coaccessible subautomaton.

Computes a fresh automaton with a copy of the coaccessible part of aut. If the keep_history flag is true, the result is endowed with a SINGLE history.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)
keep_history	A Boolean that tells whether the history must be registered.

Returns

A mutable Awali automaton

coaccessible_here()

template<typename Aut >

void awali::sttc::coaccessible_here

(

Aut &

aut

)

In-place coaccessible subautomaton.

Remove every non coaccessible state of aut.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static mutable Awali automaton

coaccessible_states()

template<typename Aut >

std::set<state_t> awali::sttc::coaccessible_states	(	const Aut &	aut,
		bool	include_pre_post = false
	)

List of coaccessible states.

Computes the list of coaccessible states in aut.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)
include_pre_post	if true, the pre-initial and the post-final states may be added to the result.

Returns

a standard set

codeterminize()

template<typename Aut >

auto awali::sttc::codeterminize	(	const Aut &	aut,
		bool	keep_history = true
	)		-> mutable_automaton<context_t_of<Aut>>

Co-determinization of the automaton.

Computes the transpostion of the determinization of the transposition. The determinization is actually applied to a transpose_view in order to avoid a copy.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the input automaton
keep_history	if true, every state of the result is linked to a set of states of aut return a co-deterministic automaton

compact()

template<typename Aut >

auto awali::sttc::compact	(	const Aut &	aut,
		bool	keep_history = true
	)		-> typename internal::allowworder<Aut>::ret_automaton_t

Compacts non branching paths.

This function applies compact_here to a copy of aut. If the labels of the automaton are letters, the type of the copy is enhanced in order to support words as labels.

Template Parameters

Aut	the type of the input automaton

Parameters

aut	the automaton
keep_history	if true the result is endowed with a single_history to the input automaton

Returns

an automaton with compacted paths.

compact_here()

template<typename Aut >

void awali::sttc::compact_here

(

Aut &

aut

)

Compacts non branching paths.

This in-place algorithm replace every non branching path by a transition labeled by the word formed by the labels of the path. The inner states of the path are deleted.
The labels of the automaton must support multiplication (like words).

Template Parameters

Aut	the type of the input automaton

Parameters

aut	the automaton

compact_thompson() [1/2]

template<typename Aut , typename Context = context_t_of<Aut>>

Aut awali::sttc::compact_thompson	(	const Context &	ctx,
		const typename Context::ratexp_t &	exp,
		bool	keep_history = true
	)

builds a compact variant of the Thompson automaton

This automaton has some characteristics similar to the classical Thompson automaton :

• it may have epsilon-transitions;
  
• it has a unique initial state with initial weight equal to one; this state has no incoming transitions;
  
• it has a unique final state, distinct from the initial state, with final weight equal to one; this state has no incoming transitions;
  
• the number of states and transitions is linear w.r.t. the size of the expression exp.
  Meanwhile, opposite to the Thompson automaton, neither the in-degree nor the out-degree of each state is bounded.

Actually, the following rules are applied:

• to represent the sum, the initial (resp. final) states are merged;
  
• to represent the product, the final state of the first automaton is merged with the initial state of the second one;
  
• to represent the star, the initial and the final states are merged; then a fresh initial state and a fresh final states are added.

Template Parameters

Aut	type of the generated automaton
Context	type of the context of the generated automaton

Parameters

ctx	the context of the generated automaton
exp	the rational expression
keep_history	(optional) if true (default value), the states are stamped with their origin

Returns

the compact Thompson automaton

compact_thompson() [2/2]

template<typename RatExpSet >

mutable_automaton<sttc::nullable_of<typename RatExpSet::context_t> > awali::sttc::compact_thompson	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	exp,
		bool	keep_history = true
	)

builds a compact variant of the Thompson automaton

Template Parameters

RatExpSet

type of the context of the rational expression

Parameters

rs	the context of the rational expression
exp	the rational expression
keep_history	(optional) if true (default value), the states are stamped with their origin

Returns

the compact Thompson automaton

complement()

template<typename Aut >

auto awali::sttc::complement	(	const Aut &	aut,
		bool	keep_history = true
	)		-> decltype(copy(aut))

Complementation of a deterministic complete automaton.

Applies complement_here to a copy of aut

Template Parameters

Aut	the type of the automaton

Parameters

aut	a Boolean deterministic complete automaton
keep_history	if true, every state of the result is linked to a state of aut

complement_here()

template<typename Aut >

Aut awali::sttc::complement_here

(

Aut &

aut

)

Complementation of a deterministic complete automaton.

The function swaps the final status of every state.

Template Parameters

Aut	the type of the automaton

Parameters

aut	a Boolean deterministic complete automaton

Returns

the automaton aut itself

complete()

template<typename Aut >

auto awali::sttc::complete	(	const Aut &	aut,
		bool	keep_history = true
	)		-> decltype(copy(aut, keep_history))

Completion of a deterministic automaton.

Applies complete_here to a copy of aut

Template Parameters

Aut	the type of the automaton

Parameters

aut	a Boolean deterministic automaton
keep_history	if true, every state of the result is linked to a state of aut

complete_here()

template<typename Aut >

Aut& awali::sttc::complete_here

(

Aut &

aut

)

Completion of a deterministic automaton.

The function adds if needed a sink state.

Template Parameters

Aut	the type of the automaton

Parameters

aut	a Boolean deterministic complete automaton

Returns

the automaton aut itself

components()

template<typename Aut >

const std::vector<std::unordered_set<state_t> > awali::sttc::components

(

const Aut &

aut

)

Find all strongly connected components of aut.

compose()

template<typename TDC1 , typename TDC2 >

auto awali::sttc::compose	(	const TDC1 &	tdc1,
		const TDC2 &	tdc2,
		bool	keep_history = true
	)		-> typename internal::composer<TDC1, TDC2, 1, 0>::automaton_t

Composition of two transducers.

Compose tdc1 to tdc2 two w.r.t. the second tape of tdc1 and the first tape of tdc2.
This is equivalent to composeIJ<1,0>(tdc1, tdc2)

Template Parameters

TDC1	the type of the firt transducer
TDC2	the type of the second transducer

Parameters

tdc1	the first transducer
tdc2	the second transducer
keep_history	if true, every state of the result is linked to a pair of states of tdc1 and tdc2

Returns

a transducer which is the result of the composition

composeIJ()

template<size_t I, size_t J, typename TDC1 , typename TDC2 >

auto awali::sttc::composeIJ	(	TDC1 &	tdc1,
		TDC2 &	tdc2,
		bool	keep_history = true
	)		-> typename internal::composer<TDC1, TDC2, I, J>::automaton_t

Composition of two transducers on given tapes.

This function computes the composition of the accessible part of two transducers with respect to statically specified tapes.

In order to support weighted compositions, an outsplit is applied to tdc1: for every state s, if among labels on tape I of transitions outgoing from s, there are both epsilon and non epsilon labels, this state is splitted in order to separate these classes of transitions. Then, the composition is performed with the constraint that a state with "epsilon outgoing transitions" of tdc1 can not be reached by a transition with label epsilon on tape J of tdc2. This forces to deal with epsilons first in tdc1; this non commutativity of epsilon transitions guarantees that a pair of matching computations in tdc1 and tdc2 is only represented once in the result.

In the result, the tapes of tdc1 are appened to the tapes of tdc2, except the tape I of tdc1 and the tape J of tdc2 which are deleted.

Template Parameters

I	the index of the composing tape of the first transducer
J	the index of the composing tape of the second transducer
TDC1	the type of the firt transducer
TDC2	the type of the second transducer

Parameters

tdc1	the first transducer
tdc2	the second transducer
keep_history	if true, every state of the result is linked to a pair of states of tdc1 and tdc2

Returns

a transducer which is the result of the composition

concatenate() [1/2]

template<typename Aut1 , typename Aut2 >

auto awali::sttc::concatenate	(	const Aut1 &	aut1,
		const Aut2 &	aut2
	)		-> decltype(join_automata(aut1, aut2))

Concatenates two automata.

The result of this function is an automaton which realizes the Cauchy product of the series realized by the input automata.
The type of the result is the join of the types of both input automata. If the result supports epsilon transitions, the concatenation is realized by the addition of epsilon transitions between final states of aut1 to initial states of aut2, with a weight equal to the product of the final weight in aut1 by the initial weight in aut2.
Otherwise, transitions outgoing from initial states of aut2 are duplicated as transitions outgoing from final states of aut1, with the same labels and destinations; the weight of the transition is multiplied left by the initial weight in aut2 and the final weight in aut1.
In any case, the final states of aut1 are made non final and the initial state of aut2 are made non initial.

Template Parameters

Aut1	the type of the first automaton
Aut2	the type of the second automaton

Parameters

aut1	the first automaton
aut2	the second automaton

Returns

the concatenation of the automata

concatenate() [2/2]

template<typename ValueSet >

ValueSet::value_t awali::sttc::concatenate	(	const ValueSet &	vs,
		const typename ValueSet::value_t &	lhs,
		const typename ValueSet::value_t &	rhs
	)

wrapper for the multiplication of values

equivalent to vs.mul(lhs, rhs)

Template Parameters

ValueSet

the type of a value set

Parameters

vs	a value set (ratexpset, weightset, etc.)
lhs	a value in the value set
rhs	a second value in the value set

Returns

the product of lhs and rhs in vs

concatenate_here()

template<typename A , typename B >

A& awali::sttc::concatenate_here	(	A &	res,
		const B &	aut
	)

Concatenation of an automaton to another one.

The function concatenates the automaton aut to the automaton res, following the description given in concatenate.
The type of aut must be compliant with the type of res.

Template Parameters

A	the type of the modified automaton
B	the type of the added automaton

Parameters

res	the modifed automaton
aut	the added automaton

Returns

the automaton res

condensation()

template<typename Aut >

std::pair< Aut, std::pair< std::unordered_map<state_t, unsigned int>, std::vector<std::vector<state_t> > > > awali::sttc::condensation

(

Aut

aut

)

Condense each strongly connected component to a state.

A new automaton is created, where every state corresponds to a scc of the input aut.
Let s(p) be the state of the result corresponding to the scc of the state p of aut; for every transition from p to q in aut, a transition with the same label and the same weight, from s(p) to s(q) is added to the result.
In particular, the initial (resp. final) weight of s(p) is the sum of the initial (resp. final) weights of the states of the scc of p.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the automaton

Returns

a pair where the first component is the condensed automaton, and the second one is a pair where the first component is a map from states into strongly connected components, and the second component gives, for each scc, the list of its states.

constant_term()

template<typename RatExpSet >

weight_t_of<RatExpSet> awali::sttc::constant_term	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e
	)

conv()

template<typename ValueSet , typename... Args>

auto awali::sttc::conv	(	const ValueSet &	vs,
		const std::string &	str,
		Args &&...	args
	)		-> decltype(vs.conv(std::declval<std::istream&>(), std::forward<Args>(args)...))

Parse str via vs.conv.

copy() [1/3]

template<typename AutIn , typename AutOut = typename AutIn::element_type::automaton_nocv_t>

AutOut awali::sttc::copy	(	const AutIn &	input,
		bool	keep_history = true,
		bool	transpose = false
	)

A copy of input.

copy() [2/3]

template<typename AutIn , typename AutOut = typename AutIn::element_type::automaton_nocv_t>

AutOut awali::sttc::copy	(	const AutIn &	input,
		const std::set< state_t > &	keep,
		bool	keep_history = true,
		bool	transpose = false
	)

A copy of input keeping only its states that are members of keep.

copy() [3/3]

template<typename AutIn , typename AutOut = typename AutIn::element_type::automaton_nocv_t, typename Pred >

AutOut awali::sttc::copy	(	const AutIn &	input,
		Pred	keep_state,
		bool	keep_history = true,
		bool	transpose = false
	)

A copy of input keeping only its states that are accepted by keep_state.

copy_into() [1/2]

template<typename AutIn , typename AutOut >

void awali::sttc::copy_into	(	const AutIn &	in,
		AutOut &	out,
		bool	keep_history = true,
		bool	transpose = false
	)

copy_into() [2/2]

template<typename AutIn , typename AutOut , typename Pred >

void awali::sttc::copy_into	(	const AutIn &	in,
		AutOut &	out,
		Pred	keep_state,
		bool	keep_history = true,
		bool	transpose = false
	)

Copy an automaton.

Precondition

AutIn <: AutOut.

copy_support() [1/2]

template<typename AutIn , typename AutOut >

void awali::sttc::copy_support	(	const AutIn &	in,
		AutOut &	out,
		bool	keep_history = true
	)

copy_support() [2/2]

template<typename AutIn , typename AutOut , typename Pred >

void awali::sttc::copy_support	(	const AutIn &	in,
		AutOut &	out,
		Pred	keep_state,
		bool	keep_history = true
	)

cycle_identity()

template<typename Aut >

bool awali::sttc::cycle_identity	(	const std::unordered_set< state_t > &	c,
		const Aut &	aut
	)

Check the weight of two states on this component is unique.

daut()

template<typename Aut >

std::ostream& awali::sttc::daut	(	const Aut &	aut,
		std::ostream &	out
	)

Output in 'daut' format.

An extension of dot for automata

del_epsilon_trans()

template<typename Aut >

void awali::sttc::del_epsilon_trans	(	Aut	a,
		state_t	src,
		state_t	dst
	)

Helper to delete an epsilon transition.

Like the del_transition method of automata, this function removes, if it exists, the epsilon transition with the given ends.

Template Parameters

Aut	the type of the automaton

Parameters

a	the automaton
src	the source state of the transition
dst	the destination state of the transition

Exceptions

runtime_error

if the automaton does not admit epsilon transitions

derivation() [1/3]

template<typename RatExpSet >

rat::ratexp_polynomial_t<RatExpSet> awali::sttc::derivation	(	const RatExpSet &	rs,
		const rat::ratexp_polynomial_t< RatExpSet > &	p,
		label_t_of< RatExpSet >	a,
		bool	breaking = false
	)

Derive a polynomial of ratexps wrt to a letter.

derivation() [2/3]

template<typename RatExpSet >

rat::ratexp_polynomial_t<RatExpSet> awali::sttc::derivation	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e,
		const typename sttc::labelset_trait< typename RatExpSet::labelset_t >::wordset_t::word_t &	word,
		bool	breaking = false
	)

Derive a ratexp wrt to a word.

derivation() [3/3]

template<typename RatExpSet >

rat::ratexp_polynomial_t<RatExpSet> awali::sttc::derivation	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e,
		label_t_of< RatExpSet >	a,
		bool	breaking = false
	)

Derive a ratexp wrt to a letter.

derived_term()

template<typename RatExpSet >

mutable_automaton<typename RatExpSet::context_t> awali::sttc::derived_term	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	r,
		bool	breaking = false,
		bool	keep_history = true
	)

Derive a ratexp wrt to a string.

determinize()

template<typename Aut >

auto awali::sttc::determinize	(	const Aut &	a,
		bool	keep_history = true
	)		-> mutable_automaton<context_t_of<Aut>>

Determinization of the automaton.

The determinization is computed with the subset construction. If the number of states of a is small (not larger than twice the number of digits of size_t, every subset is represented by a bitset, otherwise, it is represented by a std::set.

Template Parameters

Aut	the type of the automaton

Parameters

a	the input automaton
keep_history	if true, every state of the result is linked to a set of states of a return a deterministic automaton

difference()

template<typename Lhs , typename Rhs >

Lhs::element_type::automaton_nocv_t awali::sttc::difference	(	const Lhs &	aut1,
		const Rhs &	aut2
	)

Computes an automaton that accepts every word accepted by aut1 which is not accepted by aut2.

If aut1 is a weighted automaton, the result realizes the series restricted to the complement of the language recognized by aut2.

Parameters

aut1	an automaton labeled by letters
aut2	a Boolean automaton labeled by letters

Returns

an automaton

divkbaseb()

template<typename Context >

mutable_automaton<Context> awali::sttc::divkbaseb	(	const Context &	ctx,
		unsigned	divisor,
		unsigned	base
	)

Returns an automaton which recognizes numbers in the given base which are multiple of divisor.

The factory builds a deterministic automaton with divisor states. If the alphabet has more than base letters, the larger letters do not label any transition.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

Template Parameters

Context

the type of the context

Parameters

ctx	the context of the automaton
divisor	a positive integer
base	a positive integer

Returns

an automaton with divisor states

Exceptions

runtime_error

if divisor is not positive, or if base is smaller than 2, or if the alphabet has less than base letters

dot()

template<typename Aut >

std::ostream& awali::sttc::dot	(	const Aut &	aut,
		std::ostream &	out,
		bool	dot2tex = false,
		bool	keep_history = true,
		bool	horizontal = true
	)

double_ring()

template<class Context >

mutable_automaton<Context> awali::sttc::double_ring	(	const Context &	ctx,
		unsigned	n,
		const std::vector< unsigned > &	finals
	)

Returns a double ring automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z.

The context specifies both the alphabet and the weightset.

For every state p,

• the first letter of the alphabet labels transitions from p to p+1;
  
• the second one labels transitions from p to p-1;
• if the alphabet has more than 2 letters, the other letters do not label any transition.

State 0 is initial; finals is the list of the final states.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

Template Parameters

Context

the type of the context

Parameters

ctx	the context of the automaton
n	a positive integer
finals	a vector of states

Returns

an automaton with n states

Exceptions

runtime_error

if n is not positive or if alphabet has less than 2 letters

draw_exp()

template<typename RatExpSet >

mutable_automaton<context<ctx::law_char, b> > awali::sttc::draw_exp	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	exp
	)

eat() [1/2]

void awali::sttc::eat	(	std::istream &	is,
		char	c
	)

Check lookahead character and advance.

Parameters

is	the stream to read.
c	the expected character.

Exceptions

std::runtime_error

if the next character is not c.

eat() [2/2]

void awali::sttc::eat	(	std::istream &	is,
		const std::string &	expect
	)

Check lookahead string and advance.

Parameters

is	the stream to read.
expect	the expected string.

Exceptions

std::runtime_error

if the next character is not s.

efsm()

template<typename Aut >

std::ostream& awali::sttc::efsm	(	const Aut &	aut,
		std::ostream &	out
	)

Format automaton to EFSM format, based on FSM format.

Template Parameters

Aut	an automaton type.

enumerate()

template<typename Automaton >

internal::enumerater<Automaton>::polynomial_t awali::sttc::enumerate	(	const Automaton &	aut,
		unsigned	max_length
	)

Gives the weight associated with each word shorter than max_length by aut.

Template Parameters

Automaton

type

Parameters

aut	the automaton
max_length	the maximal length of words

Returns

a polynomial which is a map from words to weights.

Precondition

The labelset of the automaton aut must be free.

equals()

template<class RatExpSet >

RatExpSet::ratexp_t awali::sttc::equals	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	v
	)

eval()

template<typename Aut >

auto awali::sttc::eval	(	const Aut &	a,
		const typename labelset_trait< labelset_t_of< Aut >>::wordset_t::word_t &	w,
		bool	check_alphabet = true
	)		-> weight_t_of<Aut>

eval_tdc()

template<typename Aut , typename Tdc >

auto awali::sttc::eval_tdc	(	const Aut &	aut,
		const Tdc &	tdc,
		bool	keep_history = true
	)		-> decltype(projection<1>(tdc))

Evaluation of an automaton by a transducer.

The evaluation is made by composition of the automaton with respect to the first tape of the transducer.
The result corresponds then to the second tape of the input transducer.

Template Parameters

Aut	the type of the automaton
Tdc	the type of the transducer

Parameters

aut	the automaton
tdc	the transducer
keep_history	if true, every state of the result is linked to a pair of states of aut and tdc

Returns

an automaton

eval_words_in_tdc()

template<typename Tdc >

auto awali::sttc::eval_words_in_tdc	(	const Tdc &	tdc,
		const typename internal::select< labelset_t_of< Tdc >, 0 >::labelset_t::word_t &	w1,
		const typename internal::select< labelset_t_of< Tdc >, 1 >::labelset_t::word_t &	w2
	)		-> weight_t_of<Tdc>

exp_stats()

template<typename RatExpSet >

exp_stats_t awali::sttc::exp_stats	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	exp
	)

computes some statistics on a rational expression

Template Parameters

RatExpSet

type of the context of the rational expression

Parameters

rs	the context of the rational expression
exp	the rational expression

Returns

a exp_stats_t structure that contains the statistics

The function computes

• the size: the number of nodes in exp,
• the length : the number of leaves (different from Zero or One),
  
• the height of the expression exp as a tree,
  
• the star height of exp: the maximum number of nested stars.
  The context rs is used to produce the visitor that computes these statistics.

expand()

template<typename RatExpSet >

RatExpSet::value_t awali::sttc::expand	(	const RatExpSet &	rs,
		const typename RatExpSet::value_t &	e
	)

Expanding a typed ratexp shared_ptr.

explore_by_length()

template<typename Aut >

auto awali::sttc::explore_by_length	(	const Aut &	aut,
		unsigned	depth
	)		-> mutable_automaton<context_t_of<Aut>>

Exploration of the automaton up to a given depth.

The result is a deterministic automaton where the weight of the word is given by the final function. The result is a restriction of the determinization to the states at distance at most depth of the initial state.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the input automaton
depth	the depth of the exploration return a deterministic automaton

explore_with_bound()

template<typename Aut >

auto awali::sttc::explore_with_bound	(	const Aut &	aut,
		typename weightset_t_of< Aut >::value_t	bound
	)		-> mutable_automaton<context_t_of<Aut>>

Exploration of the automaton up to a given bound.

The result is a deterministic automaton where the weight of the word is given by the final function. The result is a restriction of the determinization to the states corresponding to multisets of states where no weight is larger than bound. The comparison is made through the less_than method of the weightset applied to the square of the component and the square of the bound.

Caveat : in zmin, the ordering of the weightset is opposite to the natural way, such that zero (=oo) is smaller than one (=0).

Template Parameters

Aut	the type of the automaton

Parameters

aut	the input automaton
bound	the bound for the exploration return a deterministic automaton

factor()

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::factor	(	const Aut &	a,
		bool	keep_history = true
	)

factor_here()

template<typename Aut >

void awali::sttc::factor_here

(

Aut &

a

)

Make each useful state both initial and final.

fado()

template<typename Aut >

std::ostream& awali::sttc::fado	(	const Aut &	aut,
		std::ostream &	out
	)

fail_reading()

ATTRIBUTE_NORETURN void awali::sttc::fail_reading	(	std::istream &	is,
		std::string	explanation
	)

Throw an exception after failing to read from is.

Reset the stream to a "good" state, and read the presumably ill-formed input into a buffer string; then throw std::domain_error with the given explanation followed by the buffer string. explanation should not contain trailing punctuation or spaces.

fill_with_accessible_states()

template<typename Set , typename Aut >

void awali::sttc::fill_with_accessible_states	(	Set &	res,
		const Aut &	aut,
		bool	include_pre_post = false
	)

fill_with_coaccessible_states()

template<typename Set , typename Aut >

void awali::sttc::fill_with_coaccessible_states	(	Set &	res,
		const Aut &	aut,
		bool	include_pre_post = false
	)

format()

template<typename ValueSet , typename... Args>

auto awali::sttc::format	(	const ValueSet &	vs,
		const typename ValueSet::value_t &	v,
		Args &&...	args
	)		-> std::string

Format v via vs.print.

get_entry()

template<typename Aut >

polynomialset<context_t_of<Aut> >::value_t awali::sttc::get_entry	(	const Aut &	aut,
		state_t	s,
		state_t	d
	)

The entry between two states of an automaton.

get_epsilon()

ctx::lan_char::value_t awali::sttc::get_epsilon

(

)

Helper to get the value of epsilon.

Template Parameters

Labelset

the label set

Returns

the value of epsilon

Exceptions

runtime_error

if the label set does not admit epsilon transitions

get_file_contents()

std::string awali::sttc::get_file_contents

(

const std::string &

file

)

Return the contents of file.

get_letterset()

template<typename L >

auto awali::sttc::get_letterset

(

const L &

labelset

)

-> typename labelset_trait<L>::letterset_t

get_letterset_context()

template<typename LS , typename WS >

auto awali::sttc::get_letterset_context

(

const context< LS, WS > &

ctx

)

-> context<typename labelset_trait<LS>::letterset_t, WS>

get_not_nullable_context()

template<typename Context >

auto awali::sttc::get_not_nullable_context

(

const Context &

ctx

)

-> not_nullable_of<Context>

get_not_nullableset()

template<typename L >

auto awali::sttc::get_not_nullableset

(

const L &

labelset

)

-> typename labelset_trait<L>::not_nullable_t

get_nullable_context()

template<typename Context >

auto awali::sttc::get_nullable_context

(

const Context &

ctx

)

-> nullable_of<Context>

get_nullableset()

template<typename L >

auto awali::sttc::get_nullableset

(

const L &

labelset

)

-> typename labelset_trait<L>::nullable_t

get_rat_context()

template<typename Context >

ratexp_context_of<Context> awali::sttc::get_rat_context

(

const Context &

ctx

)

get_ratexpset()

template<typename AUTOMATON >

auto awali::sttc::get_ratexpset

(

AUTOMATON &

aut

)

-> ratexpset_of<context_t_of<AUTOMATON>>

get_ratlabelset()

template<typename L >

auto awali::sttc::get_ratlabelset

(

const L &

labelset

)

-> typename labelset_trait<L>::ratlabelset_t

get_union()

template<typename L2 >

set_alphabet<L2> awali::sttc::get_union	(	const set_alphabet< L2 > &	lhs,
		const set_alphabet< L2 > &	rhs
	)

get_wordset()

template<typename L >

auto awali::sttc::get_wordset

(

const L &

labelset

)

-> typename labelset_trait<L>::wordset_t

get_wordset_context()

template<typename LS , typename WS >

auto awali::sttc::get_wordset_context

(

const context< LS, WS > &

ctx

)

-> context<typename labelset_trait<LS>::wordset_t, WS>

grail()

template<typename Aut >

std::ostream& awali::sttc::grail	(	const Aut &	aut,
		std::ostream &	out
	)

has_twins_property()

template<typename Aut >

bool awali::sttc::has_twins_property

(

const Aut &

aut

)

Whether aut has the twins property.

hopcroft_det()

template<typename Aut >

void awali::sttc::hopcroft_det	(	const Aut &	aut,
		std::vector< std::vector< state_t > > &	states_in_part
	)

minimization with Hopcroft for incomplete deterministic automata

(cf. Beal & Crochemore, Minimizing incomplete automata, 2008)

Template Parameters

Aut	the type of the automaton

Parameters

aut	a Boolean deterministic automaton
states_in_part	a partition of states (which is initialized in the algorithm)

hopcroft_quotient()

template<typename Aut >

unsigned awali::sttc::hopcroft_quotient	(	const Aut &	aut,
		std::vector< std::list< state_t > > &	states_in_part,
		bool	cancellative = false
	)

images()

template<typename Tdc >

auto awali::sttc::images	(	const Tdc &	in,
		bool	keep_history = true
	)		-> typename internal::imagers<Tdc>::out_automaton_t

Projection of last tapes of a transducer.

Template Parameters

Tdc	the type of the transducer

Parameters

in	a transducer
keep_history	if true the result is endowed with a single_history to the input transducer

Returns

a transducer obtained from in by deleting the first tape

in_situ_remover()

template<typename Aut >

bool awali::sttc::in_situ_remover	(	Aut &	aut,
		bool	prune = true
	)

Blindly eliminate epsilon transitions without checking for the validity of the automaton.

Return true iff the process worked.

infiltration()

template<typename Lhs , typename Rhs >

auto awali::sttc::infiltration	(	const Lhs &	lhs,
		const Rhs &	rhs,
		bool	keep_history = true
	)		-> decltype(join_automata(lhs, rhs))

Build the (accessible part of the) infiltration.

info() [1/2]

template<class A >

std::ostream& awali::sttc::info	(	const A &	aut,
		std::ostream &	out,
		bool	detailed = false
	)

info() [2/2]

template<class RatExpSet >

void awali::sttc::info	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e,
		std::ostream &	o
	)

intersection()

template<typename L2 >

set_alphabet<L2> awali::sttc::intersection	(	const set_alphabet< L2 > &	lhs,
		const set_alphabet< L2 > &	rhs
	)

inverse()

template<typename Aut >

auto awali::sttc::inverse

(

const Aut &

aut

)

-> decltype(::sttc::copy(aut))

inverse_here()

template<typename Aut >

Aut& awali::sttc::inverse_here

(

Aut &

aut

)

Inverse the weight of all edges of aut.

is_accessible()

template<typename Aut >

bool awali::sttc::is_accessible

(

const Aut &

aut

)

Test whether every state of the automaton is accessible.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)

Returns

true if every state is accessible; false otherwise.

is_acyclic()

template<typename Aut >

ATTRIBUTE_CONST bool awali::sttc::is_acyclic

(

const Aut &

aut

)

is_ambiguous()

template<typename Aut >

bool awali::sttc::is_ambiguous

(

const Aut &

aut

)

is_coaccessible()

template<typename Aut >

bool awali::sttc::is_coaccessible

(

const Aut &

aut

)

Test whether every state of the automaton is coaccessible.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)

Returns

true if every state is coaccessible; false otherwise.

is_complete()

template<typename Aut >

bool awali::sttc::is_complete

(

const Aut &

aut

)

Whether aut is complete.

Precondition

aut is LTL

is_congruence()

template<typename Aut >

bool awali::sttc::is_congruence	(	const Aut &	aut,
		const std::vector< std::vector< state_t >> &	partition
	)

is_deterministic()

template<class Aut >

bool awali::sttc::is_deterministic

(

const Aut &

aut

)

tests whether the automaton is deterministic

This function does not consider weights; weighted automata are supported yet.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the input automaton return true if the automaton has at most one initial state, and for every state s and every label l, l labels at most one transoition outgoing from s

is_empty()

template<typename Aut >

bool awali::sttc::is_empty

(

const Aut &

aut

)

Test whether the automaton has no state.

Beware that the automaton may have a transition from pre_ to post_

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)

Returns

true if the automaton has no state; false otherwise.

is_eps_acyclic()

template<typename Aut >

ATTRIBUTE_CONST bool awali::sttc::is_eps_acyclic

(

const Aut &

aut

)

is_epsilon() [1/2]

template<typename Labelset >

bool awali::sttc::is_epsilon

(

const typename Labelset::value_t &

l

)

Helper to test if a label is epsilon.

Template Parameters

Labelset

the label set

Parameters

l

the label

Returns

true if the label is epsilon

Exceptions

runtime_error

if the label set does not admit epsilon transitions

is_epsilon() [2/2]

bool awali::sttc::is_epsilon

(

ctx::lan_char::value_t

v

)

is_finite()

template<typename WS >

constexpr bool awali::sttc::is_finite ( const WS &  ws )

constexpr

is_functional()

template<typename Tdc >

bool awali::sttc::is_functional

(

Tdc &

transducer

)

is_locally_finite()

template<typename WS >

constexpr bool awali::sttc::is_locally_finite ( const WS &  ws )

constexpr

is_normalized()

template<typename Aut >

bool awali::sttc::is_normalized

(

const Aut &

a

)

is_of_finite_image()

template<unsigned I, typename Tdc >

bool awali::sttc::is_of_finite_image

(

const Tdc &

tdc

)

Check whether the image of every word is finite.

The function actually tests whether there exists some circuit with label epsilon on tape I, and non empty output on the other tapes.

Template Parameters

I	the index of the tape
Tdc	the type of transducer

Parameters

tdc	the transducer

Returns

true if and only if the image of every word read on tape I is finite

is_proper()

template<typename Aut >

bool awali::sttc::is_proper

(

const Aut &

aut

)

Test whether an automaton is proper.

An automaton is proper iff it contains no epsilon-transition.

Parameters

aut	The tested automaton

Returns

true iff the automaton is proper

is_proper_tape()

template<size_t I, typename Tdc >

bool awali::sttc::is_proper_tape

(

const Tdc &

tdc

)

is_quotient()

template<typename Aut1 , typename Aut2 >

bool awali::sttc::is_quotient	(	const Aut1 &	a1,
		const Aut2 &	a2
	)

is_realtime()

template<typename Tdc >

bool awali::sttc::is_realtime

(

const Tdc &

tdc

)

is_sequential()

template<class Aut >

bool awali::sttc::is_sequential

(

const Aut &

aut

)

tests whether the automaton is deterministic

This function does not consider weights; weighted automata are supported yet.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the input automaton return true if the automaton has at most one initial state, and for every state s and every label l, l labels at most one transoition outgoing from s

is_sequential_tdc()

template<typename Tdc >

bool awali::sttc::is_sequential_tdc

(

const Tdc &

tdc

)

is_standard()

template<typename Aut >

bool awali::sttc::is_standard

(

const Aut &

a

)

is_synchronizable()

template<typename Tdc >

bool awali::sttc::is_synchronizable

(

Tdc

tdc

)

is_synchronized_by()

template<typename Aut >

bool awali::sttc::is_synchronized_by	(	const Aut &	aut,
		const typename labelset_t_of< Aut >::word_t &	w
	)

is_synchronizing()

template<typename Aut >

bool awali::sttc::is_synchronizing

(

const Aut &

aut

)

is_trim()

template<typename Aut >

bool awali::sttc::is_trim

(

const Aut &

aut

)

Test whether the automaton is trim.

Parameters

aut	A static Awali automaton that can be read-only (including view)

Returns

true if the automaton is trim; false otherwise.

is_useless()

template<typename Aut >

bool awali::sttc::is_useless

(

const Aut &

aut

)

Test whether the automaton has useful states.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)

Returns

true if the automaton has no useful state; false otherwise.

is_valid() [1/2]

template<typename Aut >

bool awali::sttc::is_valid

(

const Aut &

aut

)

Tests if aut is valid.

This function tests if the automaton aut is valid. An automaton is valid if, for every input, the sum of weights of accepting paths labeled by this input is defined.

Automata without epsilon-transitions are always valid. An automaton where the number of accepting paths is finite for every input is valid; thus if the subgraph of epsilon-transitions is acyclic, the automaton is valid.

If the subgraph of epsilon-transitions has cycles, the behaviour depends on the nature of the weightset:

– starrable: the star is defined for every element, thus every automaton is valid; such weightsets are B or N[k];
– non_starrable: the star is defined for no element except zero, thus the automaton is not valid if there are epsilon-cycles; Z or Z/nZ are such weightsets;
– tops (topologically ordered positive semirings) : positive semirings where the domain of star is downward closed, e.g. Q+, R+, tropical semirings,... in this case, the proper algorithm is performed; it fails if and only if the automaton is not valid;
– absval: semirings where absolute value allows to defined absolute summations; this brings back to the case of tops.

Parameters

aut	The tested automaton

Returns

true if and only if the automaton is valid

is_valid() [2/2]

template<typename RatExpSet >

bool awali::sttc::is_valid	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e
	)

join() [1/79]

b awali::sttc::join	(	const b &	,
		const b &
	)

join() [2/79]

c awali::sttc::join	(	const b &	,
		const c &
	)

join() [3/79]

maxmin awali::sttc::join	(	const b &	,
		const maxmin &
	)

join() [4/79]

n awali::sttc::join	(	const b &	,
		const n &
	)

join() [5/79]

noo awali::sttc::join	(	const b &	,
		const noo &
	)

join() [6/79]

pmax awali::sttc::join	(	const b &	,
		const pmax &
	)

join() [7/79]

q awali::sttc::join	(	const b &	,
		const q &
	)

join() [8/79]

r awali::sttc::join	(	const b &	,
		const r &
	)

join() [9/79]

z awali::sttc::join	(	const b &	,
		const z &
	)

join() [10/79]

zmax awali::sttc::join	(	const b &	,
		const zmax &
	)

join() [11/79]

zmin awali::sttc::join	(	const b &	,
		const zmin &
	)

join() [12/79]

template<typename Context >

ratexpset<Context> awali::sttc::join	(	const b &	a,
		const ratexpset< Context > &	b
	)

join() [13/79]

c awali::sttc::join	(	const c &	,
		const b &
	)

join() [14/79]

c awali::sttc::join	(	const c &	,
		const c &
	)

join() [15/79]

c awali::sttc::join	(	const c &	,
		const n &
	)

join() [16/79]

c awali::sttc::join	(	const c &	,
		const q &
	)

join() [17/79]

c awali::sttc::join	(	const c &	,
		const r &
	)

join() [18/79]

c awali::sttc::join	(	const c &	,
		const z &
	)

join() [19/79]

template<typename LhsLabelSet , typename LhsWeightSet , typename RhsLabelSet , typename RhsWeightSet >

auto awali::sttc::join	(	const context< LhsLabelSet, LhsWeightSet > &	a,
		const context< RhsLabelSet, RhsWeightSet > &	b
	)		-> context<join_t<LhsLabelSet, RhsLabelSet>, join_t<LhsWeightSet, RhsWeightSet>>

The join of two contexts.

join() [20/79]

f2 awali::sttc::join	(	const f2 &	,
		const f2 &
	)

join() [21/79]

template<typename GenSet >

letterset<GenSet> awali::sttc::join	(	const letterset< GenSet > &	lhs,
		const letterset< GenSet > &	rhs
	)

Compute the join with another labelset.

join() [22/79]

template<typename GenSet >

nullableset<letterset<GenSet> > awali::sttc::join	(	const letterset< GenSet > &	lhs,
		const nullableset< letterset< GenSet >> &	rhs
	)

join() [23/79]

template<typename GenSet1 , typename Ctx2 >

auto awali::sttc::join	(	const letterset< GenSet1 > &	a,
		const ratexpset< Ctx2 > &	b
	)		-> ratexpset<context<join_t<letterset<GenSet1>, labelset_t_of<Ctx2>>, weightset_t_of<Ctx2>>>

join() [24/79]

maxmin awali::sttc::join	(	const maxmin &	,
		const b &
	)

join() [25/79]

maxmin awali::sttc::join	(	const maxmin &	,
		const maxmin &
	)

join() [26/79]

n awali::sttc::join	(	const n &	,
		const b &
	)

join() [27/79]

c awali::sttc::join	(	const n &	,
		const c &
	)

join() [28/79]

n awali::sttc::join	(	const n &	,
		const n &
	)

join() [29/79]

q awali::sttc::join	(	const n &	,
		const q &
	)

join() [30/79]

r awali::sttc::join	(	const n &	,
		const r &
	)

join() [31/79]

z awali::sttc::join	(	const n &	,
		const z &
	)

join() [32/79]

template<unsigned K>

nn<K> awali::sttc::join	(	const nn< K > &	,
		const nn< K > &
	)

join() [33/79]

noo awali::sttc::join	(	const noo &	,
		const b &
	)

join() [34/79]

noo awali::sttc::join	(	const noo &	,
		const noo &
	)

join() [35/79]

template<typename GenSet >

nullableset<letterset<GenSet> > awali::sttc::join	(	const nullableset< letterset< GenSet >> &	lhs,
		const letterset< GenSet > &	rhs
	)

join() [36/79]

template<typename GenSet >

nullableset<letterset<GenSet> > awali::sttc::join	(	const nullableset< letterset< GenSet >> &	lhs,
		const nullableset< letterset< GenSet >> &	rhs
	)

compute the join with another labelset.

join() [37/79]

template<typename Lls , typename Rls >

auto awali::sttc::join	(	const nullableset< Lls > &	lhs,
		const nullableset< Rls > &	rhs
	)		-> nullableset<decltype(join(*lhs.labelset(), *rhs.labelset()))>

join() [38/79]

oneset awali::sttc::join	(	const oneset &	,
		const oneset &
	)

The union of two labelsets.

join() [39/79]

pmax awali::sttc::join	(	const pmax &	,
		const b &
	)

join() [40/79]

pmax awali::sttc::join	(	const pmax &	,
		const pmax &
	)

join() [41/79]

template<typename PLS1 , typename PWS1 , typename PLS2 , typename PWS2 >

auto awali::sttc::join	(	const polynomialset< context< PLS1, PWS1 >> &	p1,
		const polynomialset< context< PLS2, PWS2 >> &	p2
	)		-> polynomialset<context<join_t<PLS1, PLS2>, join_t<PWS1, PWS2>>>

join() [42/79]

template<typename PLS1 , typename PWS1 , typename WS2 >

auto awali::sttc::join	(	const polynomialset< context< PLS1, PWS1 >> &	p1,
		const WS2 &	w2
	)		-> polynomialset<context<PLS1, join_t<PWS1, WS2>>>

join() [43/79]

q awali::sttc::join	(	const q &	,
		const b &
	)

join() [44/79]

c awali::sttc::join	(	const q &	,
		const c &
	)

join() [45/79]

q awali::sttc::join	(	const q &	,
		const n &
	)

join() [46/79]

q awali::sttc::join	(	const q &	,
		const q &
	)

join() [47/79]

r awali::sttc::join	(	const q &	,
		const r &
	)

join() [48/79]

q awali::sttc::join	(	const q &	,
		const z &
	)

join() [49/79]

template<typename Context >

auto awali::sttc::join	(	const q &	ws,
		const ratexpset< Context > &	rs
	)		-> join_t<ratexpset<Context>, q>

join() [50/79]

r awali::sttc::join	(	const r &	,
		const b &
	)

join() [51/79]

c awali::sttc::join	(	const r &	,
		const c &
	)

join() [52/79]

r awali::sttc::join	(	const r &	,
		const n &
	)

join() [53/79]

r awali::sttc::join	(	const r &	,
		const q &
	)

join() [54/79]

r awali::sttc::join	(	const r &	,
		const r &
	)

join() [55/79]

r awali::sttc::join	(	const r &	,
		const z &
	)

join() [56/79]

template<typename Context >

auto awali::sttc::join	(	const r &	ws,
		const ratexpset< Context > &	rs
	)		-> join_t<ratexpset<Context>, r>

join() [57/79]

template<typename Context >

ratexpset<Context> awali::sttc::join	(	const ratexpset< Context > &	a,
		const b &
	)

join() [58/79]

template<typename Context >

auto awali::sttc::join	(	const ratexpset< Context > &	rs,
		const q &	ws
	)		-> ratexpset<context<labelset_t_of<Context>, join_t<weightset_t_of<Context>, q>>>

join() [59/79]

template<typename Context >

auto awali::sttc::join	(	const ratexpset< Context > &	rs,
		const r &	ws
	)		-> ratexpset<context<labelset_t_of<Context>, join_t<weightset_t_of<Context>, r>>>

join() [60/79]

template<typename Context >

auto awali::sttc::join	(	const ratexpset< Context > &	rs,
		const z &	ws
	)		-> ratexpset<context<labelset_t_of<Context>, join_t<weightset_t_of<Context>, z>>>

join() [61/79]

template<typename Ctx1 , typename GenSet2 >

auto awali::sttc::join	(	const ratexpset< Ctx1 > &	a,
		const letterset< GenSet2 > &	b
	)		-> decltype(join(b, a))

join() [62/79]

template<typename Ctx1 , typename Ctx2 >

auto awali::sttc::join	(	const ratexpset< Ctx1 > &	a,
		const ratexpset< Ctx2 > &	b
	)		-> ratexpset<join_t<Ctx1, Ctx2>>

The union of two ratexpsets.

join() [63/79]

template<typename T , typename U >

T awali::sttc::join	(	const T &	l,
		const U &
	)

join() [64/79]

template<typename ValueSet >

auto awali::sttc::join

(

const ValueSet &

vs

)

-> ValueSet

The join of a single valueset.

Useful for variadic operator on a single argument.

join() [65/79]

template<typename ValueSet1 , typename ValueSet2 , typename ValueSet3 , typename... VSs>

auto awali::sttc::join	(	const ValueSet1 &	vs1,
		const ValueSet2 &	vs2,
		const ValueSet3 &	vs3,
		const VSs &...	vs
	)		-> decltype(join(join(vs1, vs2), vs3, vs...))

join() [66/79]

template<typename GenSet >

wordset<GenSet> awali::sttc::join	(	const wordset< GenSet > &	lhs,
		const wordset< GenSet > &	rhs
	)

Compute the union with another alphabet.

join() [67/79]

template<typename WS1 , typename PLS2 , typename PWS2 >

auto awali::sttc::join	(	const WS1 &	w1,
		const polynomialset< context< PLS2, PWS2 >> &	p2
	)		-> polynomialset<context<PLS2, join_t<WS1, PWS2>>>

join() [68/79]

z awali::sttc::join	(	const z &	,
		const b &
	)

join() [69/79]

c awali::sttc::join	(	const z &	,
		const c &
	)

join() [70/79]

z awali::sttc::join	(	const z &	,
		const n &
	)

join() [71/79]

q awali::sttc::join	(	const z &	,
		const q &
	)

join() [72/79]

r awali::sttc::join	(	const z &	,
		const r &
	)

join() [73/79]

z awali::sttc::join	(	const z &	,
		const z &
	)

join() [74/79]

template<typename Context >

auto awali::sttc::join	(	const z &	ws,
		const ratexpset< Context > &	rs
	)		-> join_t<ratexpset<Context>, z>

join() [75/79]

zmax awali::sttc::join	(	const zmax &	,
		const b &
	)

join() [76/79]

zmax awali::sttc::join	(	const zmax &	,
		const zmax &
	)

join() [77/79]

zmin awali::sttc::join	(	const zmin &	,
		const b &
	)

join() [78/79]

zmin awali::sttc::join	(	const zmin &	,
		const zmin &
	)

join() [79/79]

template<unsigned N>

zz<N> awali::sttc::join	(	const zz< N > &	,
		const zz< N > &
	)

join_automata()

template<typename... Auts>

auto awali::sttc::join_automata

(

Auts &&...

auts

)

-> decltype(make_mutable_automaton(join(auts->context()...)))

Join between automata.

js_add_metadata()

template<typename Aut >

void awali::sttc::js_add_metadata	(	Aut &	aut,
		json::object_t *	p
	)

js_parse_aut_content()

template<typename Context >

mutable_automaton<Context> awali::sttc::js_parse_aut_content	(	const Context &	context,
		json::object_t const *	p
	)

js_parse_exp_content()

template<typename RatExpSet >

RatExpSet::ratexp_t awali::sttc::js_parse_exp_content	(	const RatExpSet &	rs,
		json::node_t const *	p
	)

js_print() [1/2]

template<typename Automaton , unsigned version = version::fsm_json>

std::ostream& awali::sttc::js_print	(	Automaton	aut,
		std::ostream &	o,
		bool	full = false,
		json_ast_t	extra_metadata = json_ast::empty()
	)

js_print() [2/2]

template<typename RatExpSet , unsigned version = version::fsm_json>

std::ostream& awali::sttc::js_print	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e,
		std::ostream &	o,
		json_ast_t	extra_metadata = json_ast::empty()
	)

json_creator()

template<unsigned version = version::fsm_json>

json::object_t* awali::sttc::json_creator

(

)

json_format()

template<unsigned version = version::fsm_json>

json::object_t* awali::sttc::json_format

(

)

json_timestamp()

template<unsigned version = version::fsm_json>

json::object_t* awali::sttc::json_timestamp

(

)

k_product_no_history()

template<typename... Auts>

auto awali::sttc::k_product_no_history

(

const Auts &...

as

)

-> decltype(join_automata(as...))

Build the (accessible part of the) product.

k_product_with_history()

template<typename... Auts>

auto awali::sttc::k_product_with_history

(

const Auts &...

as

)

-> decltype(join_automata(as...))

Build the (accessible part of the) product.

k_shuffle_no_history()

template<typename... Auts>

auto awali::sttc::k_shuffle_no_history

(

const Auts &...

as

)

-> decltype(join_automata(as...))

Build the (accessible part of the) product.

k_shuffle_with_history()

template<typename... Auts>

auto awali::sttc::k_shuffle_with_history

(

const Auts &...

as

)

-> decltype(join_automata(as...))

Build the (accessible part of the) product.

label_is_zero() [1/2]

template<typename LabelSet >

bool awali::sttc::label_is_zero	(	const LabelSet &	,
			...
	)

label_is_zero() [2/2]

template<typename LabelSet >

auto awali::sttc::label_is_zero	(	const LabelSet &	ls,
		const typename LabelSet::value_t *	l
	)		-> decltype(ls.is_zero(l), bool())

ladybird()

template<class Context >

mutable_automaton<Context> awali::sttc::ladybird	(	const Context &	ctx,
		unsigned	n
	)

Returns a "ladybird" automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z.
For every state p,

• the first letter of the alphabet labels transitions from p to p+1;
  
• the second letter of the alphabet labels transitions from p to p;
  
• the third letter of the alphabet labels transitions from p to p and from p to 0;
  – If the alphabet has more than 3 letters, the other letters do not label any transition. State 0 is both initial and final.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

The minimal automaton of the language accepted by ladybird n has 2^n states.
The name ladybird comes from the shape of the 6-state automaton.

Template Parameters

Context

the type of the context

Parameters

ctx	the context of the automaton
n	a positive integer

Returns

an automaton with n states

Exceptions

runtime_error

if n is not positive or if the alphabet has less than 3 letters

left_mult() [1/2]

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::left_mult	(	const Aut &	aut,
		const weight_t_of< Aut > &	w,
		bool	standard = false
	)

left_mult() [2/2]

template<typename RatExpSet >

RatExpSet::ratexp_t awali::sttc::left_mult	(	const RatExpSet &	rs,
		const weight_t_of< RatExpSet > &	w,
		const typename RatExpSet::value_t &	r
	)

left_mult_here()

template<typename Aut >

Aut& awali::sttc::left_mult_here	(	Aut &	res,
		const weight_t_of< Aut > &	w,
		bool	standard = false
	)

multiplies the initial states by a weight

Template Parameters

Aut	the type of the automaton

Parameters

res	the automaton
w	the weight
standard	if 'true' and res is a standard automaton, applies a standard multiplication

Returns

the automaton res

Exceptions

runtime_error

if standard if 'true' and res is nota standard automaton

The initial weight of every initial state of res is multiplied by w.

If standard is 'true', the initial weight remains equal to one, and the weight of every outgoing transition (and the final weight) of the initial state is multiplied by w.

left_reduce()

template<typename Aut >

Aut awali::sttc::left_reduce

(

const Aut &

input

)

less_than()

template<class RatExpSet >

RatExpSet::ratexp_t awali::sttc::less_than	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	v
	)

letterize()

template<typename Aut >

auto awali::sttc::letterize	(	const Aut &	aut,
		bool	keep_history = true
	)		-> typename internal::letterizer<Aut,labelset_t_of<Aut>>::ret_automaton_t

letterize_tape()

template<unsigned I, typename Tdc >

auto awali::sttc::letterize_tape	(	const Tdc &	tdc,
		bool	keep_history = true
	)		-> typename internal::tdc_letterizer<Tdc,I,typename labelset_t_of<Tdc>::template valueset_t<I>>::ret_transducer_t

lift() [1/2]

template<typename Aut >

internal::lifted_automaton_t<Aut> awali::sttc::lift	(	const Aut &	a,
		bool	keep_history = true
	)

Lift labels to weights.

Convert the automaton a with labels in M and weights in K into an automaton with no label (labels actually belong to the oneset labelset) and weights in K<<M>>.
Every transition p – a | k -> q is converted into a transition p' – {} | <k>a -> q'. Transitions with the same ends are converted into a single transition where the weight is the sum of the conversion of all original transitions. Moreover, the result contains two extra states I and T which respectively correspond to the "pre" and the "post" states of a. I is the only initial state; T is the only final state.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the automaton
keep_history	if true, the is an history linking every state of the result to the corresponding state of a

Returns

a normalized labelless automaton

lift() [2/2]

template<typename RatExpSet >

internal::lifted_ratexpset_t<RatExpSet>::ratexp_t awali::sttc::lift	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e
	)

lift_tdc()

template<typename Tdc >

auto awali::sttc::lift_tdc	(	const Tdc &	tdc,
		bool	keep_history = true
	)		-> typename internal::tdc_lifter<Tdc>::automaton_t

load_automaton()

template<typename T >

mutable_automaton< context< ctx::lal_char, b > > awali::sttc::load_automaton

(

std::istream &

is

)

load_automaton_with_epsilon()

template<typename T >

mutable_automaton<context<ctx::lan_char,T> > awali::sttc::load_automaton_with_epsilon

(

std::istream &

is

)

make_automaton()

template<typename T >

mutable_automaton< context< ctx::lal_char, b > > awali::sttc::make_automaton

(

const std::set< char > &

letters

)

Build an awali weighted automaton labeled by letters.

Specialization of the template function for Boolean automata (NFA)

The weightset must admit a constructor without argument.

Template Parameters

T	The type of the weightset : z, c, zz<5>, ... (must be included)

Parameters

letters

An initializer list of letters; for instance {'x','y'} @ return : an empty automaton over the weightset and the alphabet

Returns

an empty NFA over the given alphabet

make_automaton_with_epsilon()

template<typename T >

mutable_automaton< context< ctx::lan_char, b > > awali::sttc::make_automaton_with_epsilon

(

const std::set< char > &

letters

)

Build an awali weighted automaton labeled by letters with epsilon transitions.

Specialization of the template function for Boolean automata (NFA)

The weightset must admit a constructor without argument.

Template Parameters

T	The type of the weightset : z, c, zz<5>, ... (must be included)

Parameters

letters

An initializer list of letters; for instance {'x','y'} @ return : an empty automaton over the weightset and the alphabet

Returns

an empty NFA over the given alphabet

make_context()

template<typename T >

context< ctx::lal_char, b > awali::sttc::make_context

(

const std::set< char > &

letters

)

make_mutable_automaton()

template<typename Context >

mutable_automaton<Context> awali::sttc::make_mutable_automaton

(

const Context &

ctx

)

make_ordered_pair()

template<typename T >

std::pair<T, T> awali::sttc::make_ordered_pair	(	T	e1,
		T	e2
	)

make_ratexp()

template<typename RATEXPSET >

auto awali::sttc::make_ratexp	(	RATEXPSET &	ratset,
		const std::string &	exp
	)		-> typename RATEXPSET::ratexp_t

make_ratexpset()

template<typename T >

ratexpset_of< context< ctx::lal_char, b > > awali::sttc::make_ratexpset

(

)

make_shared_ptr()

template<typename SharedPtr , typename... Args>

SharedPtr awali::sttc::make_shared_ptr

(

Args &&...

args

)

Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type.

make_tdc_ratexpset()

template<typename T >

ratexpset_of< context< ctx::lat< ctx::lan_char, ctx::lan_char >, b > > awali::sttc::make_tdc_ratexpset

(

)

make_transducer()

template<typename T >

mutable_automaton< context< ctx::lat< ctx::lan_char, ctx::lan_char >, b > > awali::sttc::make_transducer	(	const std::set< char > &	letterA,
		const std::set< char > &	letterB
	)

make_tuple_automaton()

template<typename... Auts>

auto awali::sttc::make_tuple_automaton

(

const Auts &...

auts

)

-> tuple_automaton<Auts...>

make_tupleset()

template<typename... Valuesets>

auto awali::sttc::make_tupleset

(

std::tuple< Valuesets... >

t

)

-> tupleset<Valuesets...>

meet() [1/11]

template<typename LhsLabelSet , typename LhsWeightSet , typename RhsLabelSet , typename RhsWeightSet >

auto awali::sttc::meet	(	const context< LhsLabelSet, LhsWeightSet > &	a,
		const context< RhsLabelSet, RhsWeightSet > &	b
	)		-> context<meet_t<LhsLabelSet, RhsLabelSet>, join_t<LhsWeightSet, RhsWeightSet>>

The meet of two contexts.

meet() [2/11]

template<typename GenSet >

letterset<GenSet> awali::sttc::meet	(	const letterset< GenSet > &	lhs,
		const letterset< GenSet > &	rhs
	)

Compute the meet with another labelset.

meet() [3/11]

template<typename GenSet >

nullableset<letterset<GenSet> > awali::sttc::meet	(	const letterset< GenSet > &	lhs,
		const nullableset< letterset< GenSet >> &	rhs
	)

meet() [4/11]

template<typename GenSet >

nullableset<letterset<GenSet> > awali::sttc::meet	(	const nullableset< letterset< GenSet >> &	lhs,
		const letterset< GenSet > &	rhs
	)

meet() [5/11]

template<typename GenSet >

nullableset<letterset<GenSet> > awali::sttc::meet	(	const nullableset< letterset< GenSet >> &	lhs,
		const nullableset< letterset< GenSet >> &	rhs
	)

Compute the meet with another labelset.

meet() [6/11]

template<typename Lls , typename Rls >

auto awali::sttc::meet	(	const nullableset< Lls > &	lhs,
		const nullableset< Rls > &	rhs
	)		-> nullableset<decltype(meet(*lhs.labelset(), *rhs.labelset()))>

meet() [7/11]

oneset awali::sttc::meet	(	const oneset &	,
		const oneset &
	)

The meet of two labelsets.

meet() [8/11]

template<typename Ctx1 , typename Ctx2 >

auto awali::sttc::meet	(	const ratexpset< Ctx1 > &	a,
		const ratexpset< Ctx2 > &	b
	)		-> ratexpset<meet_t<Ctx1, Ctx2>>

The meet of two ratexpsets.

meet() [9/11]

template<typename ValueSet >

auto awali::sttc::meet

(

const ValueSet &

vs

)

-> ValueSet

The meet of a single valueset.

Useful for variadic operator on a single argument.

meet() [10/11]

template<typename ValueSet1 , typename ValueSet2 , typename ValueSet3 , typename... VSs>

auto awali::sttc::meet	(	const ValueSet1 &	vs1,
		const ValueSet2 &	vs2,
		const ValueSet3 &	vs3,
		const VSs &...	vs
	)		-> decltype(meet(meet(vs1, vs2), vs3, vs...))

meet() [11/11]

template<typename GenSet >

wordset<GenSet> awali::sttc::meet	(	const wordset< GenSet > &	lhs,
		const wordset< GenSet > &	rhs
	)

Compute the meet with another alphabet.

meet_automata()

template<typename... Auts>

auto awali::sttc::meet_automata

(

Auts &&...

auts

)

-> decltype(make_mutable_automaton(meet(auts->context()...)))

Meet between automata.

merge()

template<typename Aut , typename StateList >

auto awali::sttc::merge	(	const Aut &	a,
		std::vector< StateList > &	classes,
		bool	keep_history = true
	)		-> Aut

min_quotient()

template<typename Aut >

Aut awali::sttc::min_quotient	(	const Aut &	aut,
		quotient_algo_t	algo = MOORE,
		bool	keep_history = true
	)

min_quotient_det()

template<typename Aut >

Aut awali::sttc::min_quotient_det	(	const Aut &	aut,
		quotient_algo_t	algo = MOORE,
		bool	keep_history = true
	)

minimize()

template<typename Aut >

Aut awali::sttc::minimize	(	const Aut &	aut,
		quotient_algo_t	algo = MOORE,
		bool	keep_history = true
	)

minimize_brzozowski()

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::minimize_brzozowski

(

const Aut &

a

)

moore_det()

template<typename Aut >

void awali::sttc::moore_det	(	const Aut &	aut,
		std::vector< std::vector< state_t > > &	states_in_part
	)

Moore algorithm for the minimization of deterministic Boolean automata (DFA), not necessarily complete.

Template Parameters

Aut	the type of the automaton

Parameters

aut	a Boolean deterministic automaton
states_in_part	a partition of states (which is initialized in the algorithm)

moore_quotient()

template<typename Aut >

unsigned awali::sttc::moore_quotient	(	const Aut &	aut,
		std::vector< std::vector< state_t > > &	states_in_part
	)

new_epsilon_trans() [1/2]

template<typename Aut >

transition_t awali::sttc::new_epsilon_trans	(	Aut	a,
		state_t	src,
		state_t	dst,
		weight_t_of< Aut >	w
	)

Helper to create a new epsilon transition.

Like the new_transition method of automata, this function must be called only in the case where there is no existing epsilon transition with the same ends.

Template Parameters

Aut	the type of the automaton

Parameters

a	the automaton
src	the source state of the transition
dst	the destination state of the transition
w	the weight of the transition

Returns

the identifier of the created transition

new_epsilon_trans() [2/2]

template<typename Aut >

transition_t awali::sttc::new_epsilon_trans	(	const Aut	a,
		state_t	src,
		state_t	dst
	)

Helper to create a new epsilon transition.

Like the new_transition method of automata, this function must be called only in the case where there is no existing epsilon transition with the same ends.

Template Parameters

Aut	the type of the automaton

Parameters

a	the automaton
src	the source state of the transition
dst	the destination state of the transition

Returns

the identifier of the created transition

Exceptions

runtime_error

if the automaton does not admit epsilon transitions

next_heuristic()

template<typename Aut >

state_t awali::sttc::next_heuristic

(

const Aut &

a

)

next_in_order()

template<typename Aut >

state_t awali::sttc::next_in_order

(

const Aut &

a

)

num_accessible_states()

template<typename Aut >

size_t awali::sttc::num_accessible_states

(

const Aut &

aut

)

Number of accessible states.

Computes the number of accessible states (not counting pre-initial and post-final state).

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)

Returns

A size_t number

num_coaccessible_states()

template<typename Aut >

size_t awali::sttc::num_coaccessible_states

(

const Aut &

aut

)

Number of coaccessible states.

Computes the number of coaccessible states (not counting pre-initial and post-final state).

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)

Returns

A size_t number

num_useful_states()

template<typename Aut >

size_t awali::sttc::num_useful_states

(

const Aut &

aut

)

Number of useful states.

Computes the number of useful states (not counting pre-initial and post-final state).

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)

Returns

A size_t number

open_input_file()

std::shared_ptr<std::istream> awali::sttc::open_input_file

(

const std::string &

file

)

Open file for reading and return its autoclosing stream.

Parameters

file	the file name. "-" and "" denote stdin.

open_output_file()

std::shared_ptr<std::ostream> awali::sttc::open_output_file

(

const std::string &

file

)

Open file for writing and return its autoclosing stream.

Parameters

file	the file name. "-" and "" denote stdout.

operator!=()

bool awali::sttc::operator!=	(	empty_t	,
		empty_t
	)

operator--()

empty_t& awali::sttc::operator--

(

empty_t &

e

)

operator<()

bool awali::sttc::operator<	(	empty_t	,
		empty_t
	)

operator<=()

bool awali::sttc::operator<=	(	empty_t	,
		empty_t
	)

operator==()

bool awali::sttc::operator==	(	empty_t	,
		empty_t
	)

operator>()

bool awali::sttc::operator>	(	empty_t	,
		empty_t
	)

operator>=()

bool awali::sttc::operator>=	(	empty_t	,
		empty_t
	)

outsplit()

template<size_t I, typename Aut >

Aut awali::sttc::outsplit	(	const Aut &	aut,
		bool	keep_history = true
	)

outsplit_here() [1/2]

template<size_t I, typename Aut >

std::enable_if<!internal::select_one<labelset_t_of<Aut>,I>::has_one(), void>::type awali::sttc::outsplit_here

(

Aut &

)

outsplit_here() [2/2]

template<size_t I, typename Aut >

std::enable_if<internal::select_one<labelset_t_of<Aut>,I>::has_one(), void>::type awali::sttc::outsplit_here

(

Aut &

aut

)

pair()

template<typename Aut >

pair_automaton<Aut> awali::sttc::pair	(	const Aut &	aut,
		bool	keep_initials = false
	)

parse_exp()

template<typename RatExpSet >

RatExpSet::ratexp_t awali::sttc::parse_exp	(	const RatExpSet &	ratexpset,
		const std::string &	s,
		bool	check_complete = true,
		bool	strict_alphabet = true
	)

parser of rational expressions

Template Parameters

RatExpSet

the type of the context of rational expressions

Parameters

ratexpset	the context of rational expressions
s	the expression to parse
check_complete	if true, the parsing must encompass the whole string; otherwise, it may apply only to a suffix
strict_alphabet	if true every letter must belong to the alphabet in ratexpset, otherwise, it shall be added

Exceptions

parse_exception	if the expression is malformed
domain_error	if strict_alphabet is true and a letter does not belong to the alphabet

The string s is parsed to obtain a rational expression; the context is specified by ratexpset.

In rational expressions, the following characters are special: (,),[,],<,>,{,},?,*,+,.
The spaces are not significant, but they can be used to separate two tokens:
for instance, if letters are integers, "5 10" is the word with two letters, 5 and 10.

The rational expressions are defined by the wollowing grammar:
E --> P | E+P
P --> S | PS | P.S
S --> L | S* | S{exponent} | S?
L --> R | <weight>R
R --> A | A<weight>
A --> label | (E) | [label list]

The priority of operators results from the grammar.

Labels and weights are respectively parsed by the labelset and the weightset given by the ratexpset.
The form of the exponent is {p} or {p,q} or {p,} or {,q}, where p and q are nonnegative integers, with p<q.

Label Lists

Label lists are not available if labels are tuples; they are concatenation of labels or pairs of labels of the form a-b, where a and b are labels.
Inside label lists, the letter '-' can only appear at the end of the concatenation, otherwise, it is interpreted as separation of pairs.
If strict_alphabet is true, the complementation of label lists is available, indicated by '^' at the beginning of the list.

Special Characters

The backslash can not be used to escape special characters; it can only be used in front of 'e' and 'z' to represent respectively the empty word and the zero;

Every special character excepted [ is allowed in label lists, hence, it is a way to escape special character: for instance "[)]" is the letter ')'.
Moreover, the space is significant at the end of the list.
Notice also that (,[,{,< can be used as letters ouside character lists if there is no corresponding parenthesis at right.

Semantics

Every expression generated from E, P, S, L, R or A is interpreted as a (rational) series inductively defined as follow ( [[E]] is the interpretation of E) :

• a label is interpreted as the charateristic series of this letter;
• a label list is interpreted as the union of the labels enumerated in the list, a pair of labels a-b is the union of every letter in the interval [a;b];
  
• [[(E)]] = [[E]];
  
• [[A<weight>]] = [[A]].[[weight]];
• [[<weigth>R]] = [[weight]].[[R]];
• [[S*]] = [[S]]*;
  
• [[S?]] = [[S]] + one (the empty word of the monoid);
  
• [[S{p}]] is the p-th power of [[S]];
  [[S{p,q}]] is the sum of the powers of [[S]] from the p-th to the q-th;
  [[S{,q}]] = [[S{0,q}]];
  [[S{p,}]] = [[S{p}]].[[S*]];
  
• [[PS]] = [[P.S]] = [[P]].[[S]];
  
• [[E+P]] = [[E]]+[[P]].

partial_identity()

template<size_t I, typename Aut >

auto awali::sttc::partial_identity	(	const Aut &	in,
		bool	keep_history = true
	)		-> typename internal::partial_identiter<Aut, I>::out_automaton_t

Builds a transducer realizing the identity on a language.

Template Parameters

I	the number of tapes of the result
Aut	the type of the automaton

Parameters

in	the automaton
keep_history	if true the result is endowed with a single_history to the input automaton

Returns

a transducer with I tapes realizing the identity on the language of aut

path_bfs()

template<typename Aut >

std::vector<transition_t> awali::sttc::path_bfs	(	const Aut &	aut,
		state_t	start,
		state_t	end
	)

paths_ibfs()

template<typename Aut >

std::unordered_map<state_t, std::pair<unsigned, transition_t> > awali::sttc::paths_ibfs	(	const Aut &	aut,
		std::vector< state_t >	start
	)

power()

template<typename Aut >

auto awali::sttc::power	(	const Aut &	aut,
		unsigned	n
	)		-> typename Aut::element_type::automaton_nocv_t

prefix()

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::prefix	(	const Aut &	a,
		bool	keep_history = true
	)

prefix_here()

template<typename Aut >

void awali::sttc::prefix_here

(

Aut &

a

)

Make all coaccessible states final.

print()

template<typename RatExpSet >

std::ostream& awali::sttc::print	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e,
		std::ostream &	o,
		bool	with_dot = false
	)

product()

template<typename Lhs , typename Rhs >

auto awali::sttc::product	(	const Lhs &	lhs,
		const Rhs &	rhs,
		bool	keep_history = true
	)		-> decltype(join_automata(lhs, rhs))

projection()

template<size_t I, typename Tdc >

auto awali::sttc::projection	(	const Tdc &	in,
		bool	keep_history = true
	)		-> typename internal::projector<Tdc, I>::out_automaton_t

Projection of one tape of a transducer.

Template Parameters

I	the index of a tape
Tdc	the type of the transducer

Parameters

in	a transducer
keep_history	if true the result is endowed with a single_history to the input transducer

Returns

an automaton which is the projection of the tape I of in

projections()

template<size_t... I, typename Tdc >

auto awali::sttc::projections	(	const Tdc &	in,
		bool	keep_history = true
	)		-> typename internal::projectors<Tdc, I...>::out_automaton_t

Projection and/or permutation of tapes of a transducer.

The tapes of the result are given by the list I. They appear in the result with the same order as in the list. This function allows to delete or duplicate some tapes.

Template Parameters

I	the list of the indices of tapes
Tdc	the type of the transducer

Parameters

in	a transducer
keep_history	if true the result is endowed with a single_history to the input transducer

Returns

a transducer obtained from in with the given tapes

promote_ratexpset()

template<typename OutWeightSet , typename RatExpSet >

auto awali::sttc::promote_ratexpset	(	const RatExpSet &	ratexpset,
		const OutWeightSet &	out_weightset = OutWeightSet()
	)		-> typename rat::expcopy_visitor<RatExpSet, OutWeightSet>::out_ratexpset_t

Compute a derived ratexpset.

Template Parameters

OutWeightSet	type of the weightset of the copy
RatExpSet	type of the ratexpset of the rational expression

Parameters

ratexpset	the original ratexpset
out_weightset	the weightset of the result

Returns

a ratexpset with the same letterset and the same identities as the original ratexpset, with a weightset equal to out_weightset.

proper()

template<typename Aut >

auto awali::sttc::proper	(	const Aut &	aut,
		direction_t	dir = BACKWARD,
		bool	prune = true,
		bool	keep_history = true
	)		-> decltype(copy(aut))

Eliminate spontaneous transitions.

Raise if the input automaton is invalid.

proper_here()

template<typename Aut >

void awali::sttc::proper_here	(	Aut &	aut,
		direction_t	dir = BACKWARD,
		bool	prune = true
	)

Eliminate spontaneous transitions in place.

Raise if the automaton was not valid.

raise()

template<typename... Args>

ATTRIBUTE_NORETURN void awali::sttc::raise

(

Args &&...

args

)

Raise a runtime_error with the concatenation of args as message.

ratexp_copy() [1/2]

template<typename RatExpSet >

auto awali::sttc::ratexp_copy	(	const typename RatExpSet::ratexp_t &	exp,
		const RatExpSet &	ratexpset
	)		-> typename rat::expcopy_visitor<RatExpSet>::out_ratexp_t

copy a rational expression

Template Parameters

RatExpSet

type of the ratexpset of the rational expression

Parameters

exp	the rational expression
ratexpset	the ratexpset of the rational expression

Returns

a rational expression with the given weightset

Specialisation in the case where the copy has the same ratexpset as the parameter.

ratexp_copy() [2/2]

template<typename OutWeightSet , typename RatExpSet >

auto awali::sttc::ratexp_copy	(	const typename RatExpSet::ratexp_t &	exp,
		const RatExpSet &	ratexpset,
		const OutWeightSet &	out_weightset = OutWeightSet()
	)		-> typename rat::expcopy_visitor<RatExpSet, OutWeightSet>::out_ratexp_t

copy a rational expression

Template Parameters

OutWeightSet	type of the weightset of the copy
RatExpSet	type of the ratexpset of the rational expression

Parameters

exp	the rational expression
ratexpset	the ratexpset of the rational expression
out_weightset	the weightset of the copy

Returns

a rational expression with the given weightset

The function produces a fresh rational expression. The out_weightset must be compliant with the weightset of ratexpset. The ratexpset of the result has the same letterset and the same identities as ratexpset;

ratexp_support()

template<typename RatExpSet >

auto awali::sttc::ratexp_support	(	const typename RatExpSet::ratexp_t &	exp,
		const RatExpSet &	ratexpset
	)		-> typename rat::expsupport_visitor<RatExpSet>::out_ratexp_t

support of a rational expression

Template Parameters

RatExpSet

type of the ratexpset of the rational expression

Parameters

exp	the rational expression
ratexpset	the ratexpset of the rational expression

Returns

a Boolean rational expression

The function produces a fresh Boolean rational expression, which is a copy of exp where all weights are removed.

ratexp_to_ast()

template<typename RatExpSet , unsigned version = version::fsm_json>

json_ast_t awali::sttc::ratexp_to_ast	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e,
		json_ast_t	extra_metadata = json_ast::empty()
	)

read_label()

template<typename Context >

auto awali::sttc::read_label	(	std::istream &	is,
		const Context &	ctx
	)		-> label_t_of<Context>

read_polynomial()

template<typename Context >

auto awali::sttc::read_polynomial	(	const Context &	ctx,
		std::istream &	is
	)		-> typename polynomialset<Context>::value_t

read_weight()

template<typename Context >

auto awali::sttc::read_weight	(	const Context &	ctx,
		std::istream &	is
	)		-> weight_t_of<Context>

realtime()

template<typename Tdc >

auto awali::sttc::realtime	(	const Tdc &	tdc,
		bool	keep_history = true
	)		-> typename internal::realtimer<Tdc>::automaton_t

reduce()

template<typename Aut >

Aut awali::sttc::reduce

(

const Aut &

input

)

remove_letters()

template<typename Aut >

void awali::sttc::remove_letters	(	Aut &	aut,
		const std::set< typename labelset_t_of< Aut >::letter_t > &	letters,
		bool	del_unvalid_transitions = true
	)

Remove letters from the alphabet of the automaton.

This function modifies the context of the automaton; it removes the list of specified letters from the alphabet of the automaton

Template Parameters

Aut	the type of the automaton
Letter	the type of the letters

Parameters

aut	the automaton
letters	a set of letters
del_unvalid_transitions	if true, the transitions which carry a label that is not valid w.r.t the new alphabet are deleted

require()

template<typename... Args>

void awali::sttc::require	(	bool	b,
		Args &&...	args
	)

If b is not verified, raise an error with args as message.

reverse_postorder()

template<typename Aut >

std::stack<state_t> awali::sttc::reverse_postorder

(

const Aut &

aut

)

Get all vertices in reverse postorder.

right_mult() [1/2]

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::right_mult	(	const Aut &	aut,
		const weight_t_of< Aut > &	w
	)

right_mult() [2/2]

template<typename RatExpSet >

RatExpSet::ratexp_t awali::sttc::right_mult	(	const RatExpSet &	rs,
		const typename RatExpSet::value_t &	r,
		const weight_t_of< RatExpSet > &	w
	)

right_mult_here()

template<typename Aut >

Aut& awali::sttc::right_mult_here	(	Aut &	res,
		const weight_t_of< Aut > &	w
	)

scc_iterative()

template<typename Aut >

std::pair< std::unordered_map<state_t, unsigned int>, std::vector<std::vector<state_t> > > awali::sttc::scc_iterative

(

Aut

aut

)

Iterative computation of strongly connected components.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the automaton

Returns

a pair where the first component is a map from states into strongly connected components, and the second component gives, for each scc, the list of its states.

scc_of()

template<typename Aut >

std::vector<state_t> awali::sttc::scc_of	(	Aut	aut,
		state_t	s
	)

Computes the strongly connected component of a state.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the automaton
s	a state of aut

Returns

a vector containing all states in the same scc as s

scc_recursive()

template<typename Aut >

std::pair< std::unordered_map<state_t, unsigned int>, std::vector<std::vector<state_t> > > awali::sttc::scc_recursive

(

Aut

aut

)

Recursive computation of strongly connected components.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the automaton

Returns

a pair where the first component is a map from states into strongly connected components, and the second component gives, for each scc, the list of its states.

set_epsilon_trans() [1/2]

template<typename Aut >

transition_t awali::sttc::set_epsilon_trans	(	Aut	a,
		state_t	src,
		state_t	dst,
		weight_t_of< Aut >	w
	)

Helper to set an epsilon transition.

Like the set_transition method of automata, this function either creates or replaces an epsilon transition.

Template Parameters

Aut	the type of the automaton

Parameters

a	the automaton
src	the source state of the transition
dst	the destination state of the transition
w	the weight of the transition

Returns

the identifier of the created transition

Exceptions

runtime_error

if the automaton does not admit epsilon transitions

set_epsilon_trans() [2/2]

template<typename Aut >

transition_t awali::sttc::set_epsilon_trans	(	const Aut	a,
		state_t	src,
		state_t	dst
	)

Helper to set an epsilon transition.

Like the set_transition method of automata, this function either creates or replaces an epsilon transition.

Template Parameters

Aut	the type of the automaton

Parameters

a	the automaton
src	the source state of the transition
dst	the destination state of the transition

Returns

the identifier of the created transition

Exceptions

runtime_error

if the automaton does not admit epsilon transitions

shortest()

template<typename Automaton >

internal::enumerater<Automaton>::polynomial_t awali::sttc::shortest	(	const Automaton &	aut,
		unsigned	num
	)

Computes the weight of the num smallest words accepted by the automaton.

If less than num words are accepted by the automaton aut, the map is partially filled. In particular, if there is no accepted word, the map is empty.

Template Parameters

Automaton

Parameters

aut
num

Returns

a polynomial which is a map from words to weights.

Precondition

The labelset of the automaton aut must be free.

shuffle()

template<typename Lhs , typename Rhs >

auto awali::sttc::shuffle	(	const Lhs &	lhs,
		const Rhs &	rhs,
		bool	keep_history = true
	)		-> decltype(join_automata(lhs, rhs))

sort()

template<typename Aut , typename Compare >

void awali::sttc::sort	(	Aut	a,
		Compare	p
	)

sort_tape()

template<size_t I, typename Tdc >

void awali::sttc::sort_tape

(

Tdc

t

)

split() [1/2]

template<typename RatExpSet >

rat::ratexp_polynomial_t<RatExpSet> awali::sttc::split	(	const RatExpSet &	rs,
		const rat::ratexp_polynomial_t< RatExpSet > &	p
	)

Split a polynomial of ratexps.

split() [2/2]

template<typename RatExpSet >

rat::ratexp_polynomial_t<RatExpSet> awali::sttc::split	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e
	)

Split a ratexp.

standard() [1/3]

template<typename Aut >

Aut awali::sttc::standard	(	Aut &	aut,
		bool	keep_history = true
	)

standard() [2/3]

template<typename Aut , typename Context = context_t_of<Aut>>

Aut awali::sttc::standard	(	const Context &	ctx,
		const typename Context::ratexp_t &	e
	)

standard() [3/3]

template<typename RatExpSet >

mutable_automaton<typename RatExpSet::context_t> awali::sttc::standard	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	e
	)

standard_here()

template<typename Aut >

void awali::sttc::standard_here

(

Aut &

aut

)

Turn aut into a standard automaton.

Template Parameters

Aut	an automaton type, not a pointer type.

star()

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::star

(

const Aut &

aut

)

Star of an automaton.

star_height()

template<typename RatExpSet >

unsigned awali::sttc::star_height

(

const typename RatExpSet::ratexp_t &

e

)

Star height of a ratexp.

star_here()

template<typename Aut >

Aut& awali::sttc::star_here

(

Aut &

res

)

star_normal_form()

template<typename RatExpSet >

RatExpSet::value_t awali::sttc::star_normal_form	(	const RatExpSet &	rs,
		const typename RatExpSet::value_t &	e
	)

Star_Normal_Forming a typed ratexp shared_ptr.

str_escape() [1/4]

std::string awali::sttc::str_escape

(

const int

c

)

str_escape() [2/4]

std::string awali::sttc::str_escape

(

const std::string &

s

)

str_escape() [3/4]

std::ostream& awali::sttc::str_escape	(	std::ostream &	os,
		const int	c
	)

str_escape() [4/4]

std::ostream& awali::sttc::str_escape	(	std::ostream &	os,
		const std::string &	str
	)

sub_automaton() [1/2]

template<typename Aut >

void awali::sttc::sub_automaton	(	Aut &	aut,
		const std::set< state_t > &	sts
	)

sub_automaton() [2/2]

template<typename Aut , typename Pred >

void awali::sttc::sub_automaton	(	Aut &	aut,
		Pred	keep_state
	)

suffix()

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::suffix	(	const Aut &	a,
		bool	keep_history = true
	)

suffix_here()

template<typename Aut >

void awali::sttc::suffix_here

(

Aut &

a

)

Make all accessible states initial.

sum() [1/2]

template<typename Aut1 , typename Aut2 >

auto awali::sttc::sum	(	const Aut1 &	aut1,
		const Aut2 &	aut2,
		bool	sum_standard = false
	)		-> decltype(join_automata(aut1, aut2))

sums two automata

Template Parameters

Aut1	the type of the first automaton
Aut2	the type of the second automaton

Parameters

aut1	the first automaton
aut2	the second automaton
sum_standard	if true, and aut1 and aut2 are standard automata, the result is standard

Returns

an automaton

Exceptions

runtime_error

if sum_standard is true, and aut1 and aut2 are not standard

The context of the result is the join of the contexts of aut1 and aut2, if this join exists.

If sum_standard is false, the function computes the union of automata aut1 and aut2.
If sum_standard is true, the function checks that automata aut1 and aut2 are standard and builds the standard sum, which is the union where both initial states are merged.

sum() [2/2]

template<typename ValueSet >

ValueSet::value_t awali::sttc::sum	(	const ValueSet &	vs,
		const typename ValueSet::value_t &	lhs,
		const typename ValueSet::value_t &	rhs
	)

Sums of values.

sum_here()

template<typename Res , typename Aut >

Res& awali::sttc::sum_here	(	Res &	res,
		const Aut &	aut,
		bool	sum_standard = false
	)

Merge transitions of b into those of res.

Precondition

AutIn <: AutOut.

in_place sums two automata

Template Parameters

Res	the type of the first automaton
Aut	the type of the second automaton

Parameters

res	the first automaton
aut	the second automaton
sum_standard	if true, and aut1 and aut2 are standard automata, the result is standard

Returns

the automaton res

Exceptions

runtime_error

if sum_standard is true, and aut1 and aut2 are not standard

The type of aut must be compatible with the type of res

If sum_standard is false, the function copies aut into res.
If sum_standard is true, the function checks that automata aut1 and aut2 are standard and copies aut into res, except the initial state of aut which is merged with the initial state of res.

support_ratexpset()

template<typename RatExpSet >

auto awali::sttc::support_ratexpset

(

const RatExpSet &

ratexpset

)

-> typename rat::expsupport_visitor<RatExpSet>::out_ratexpset_t

Compute a derived ratexpset.

Template Parameters

RatExpSet

type of the ratexpset of the rational expression

Parameters

ratexpset

the original ratexpset

Returns

a ratexpset with the same letterset and the same identities as the original ratexpset, with a Boolean weightset.

synchronize()

template<typename Tdc >

Tdc awali::sttc::synchronize	(	const Tdc &	tdc,
		bool	keep_history = true
	)

synchronizing_word()

template<typename Aut >

labelset_t_of<Aut>::word_t awali::sttc::synchronizing_word	(	const Aut &	aut,
		const std::string &	algo = "greedy"
	)

thompson() [1/2]

template<typename Aut , typename Context = context_t_of<Aut>>

Aut awali::sttc::thompson	(	const Context &	ctx,
		const typename Context::ratexp_t &	exp,
		bool	keep_history = true
	)

builds a Thompson automaton

Template Parameters

Aut	type of the generated automaton
Context	type of the context of the generated automaton

Parameters

ctx	the context of the generated automaton
exp	the rational expression
keep_history	(optional) if true (default value), the states are stamped with their origin

Returns

the Thompson automaton

thompson() [2/2]

template<typename RatExpSet >

mutable_automaton<sttc::nullable_of<typename RatExpSet::context_t> > awali::sttc::thompson	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	exp,
		bool	keep_history = true
	)

builds a Thompson automaton

Template Parameters

RatExpSet

type of the context of the rational expression

Parameters

rs	the context of the rational expression
exp	the rational expression
keep_history	(optional) if true (default value), the states are stamped with their origin

Returns

the Thompson automaton

tikz()

template<typename AutPtr >

std::ostream& awali::sttc::tikz	(	const AutPtr &	aut,
		std::ostream &	out
	)

Format automaton to TikZ format.

Template Parameters

AutPtr

an automaton type.

to_lal()

template<typename Aut >

auto awali::sttc::to_lal	(	const Aut &	aut,
		direction_t	dir = BACKWARD,
		bool	prune = true,
		bool	keep_history = true
	)		-> typename internal::dispatch_lal_lan<Aut,labelset_t_of<Aut>>::l_automaton_t

to_lan()

template<typename Aut >

auto awali::sttc::to_lan	(	const Aut &	aut,
		bool	keep_history = true
	)		-> typename internal::dispatch_lal_lan<Aut,labelset_t_of<Aut>>::n_automaton_t

transpose() [1/2]

template<typename Aut , typename AutOut = typename Aut::element_type::automaton_nocv_t>

AutOut awali::sttc::transpose	(	Aut &	aut,
		bool	keep_history = true
	)

transpose() [2/2]

template<class RatExpSet >

RatExpSet::ratexp_t awali::sttc::transpose	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	v
	)

transpose_here()

template<typename Aut >

void awali::sttc::transpose_here

(

Aut &

aut

)

transpose_view()

template<typename Aut >

std::shared_ptr<internal::transpose_view_impl<Aut> > awali::sttc::transpose_view

(

std::shared_ptr< Aut >

aut

)

trim()

template<typename Aut >

Aut::element_type::automaton_nocv_t awali::sttc::trim	(	const Aut &	aut,
		bool	keep_history = true
	)

Trim subautomaton.

Computes a fresh automaton with a copy of the useful part of aut. If the keep_history flag is true, the result is endowed with a SINGLE history.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)
keep_history	A Boolean that tells whether the history must be registered.

Returns

A mutable Awali automaton

trim_here()

template<typename Aut >

void awali::sttc::trim_here

(

Aut &

aut

)

In-place trim subautomaton.

Remove every useless state of aut.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static mutable Awali automaton

universal()

template<class Aut >

Aut awali::sttc::universal

(

const Aut &

a

)

useful_states()

template<typename Aut >

std::set<state_t> awali::sttc::useful_states	(	const Aut &	aut,
		bool	include_pre_post = false
	)

List of useful states.

Computes the list of useful states in aut.

Template Parameters

Aut	The static type of automaton

Parameters

aut	A static Awali automaton that can be read-only (including view)
include_pre_post	if true, the pre-initial and the post-final states may be added to the result.

Returns

a standard set

VAUCR_WEIGHTS_BINARY() [1/3]

awali::sttc::VAUCR_WEIGHTS_BINARY	(	b	,
		z	,
		z
	)

VAUCR_WEIGHTS_BINARY() [2/3]

awali::sttc::VAUCR_WEIGHTS_BINARY	(	z	,
		b	,
		z
	)

VAUCR_WEIGHTS_BINARY() [3/3]

awali::sttc::VAUCR_WEIGHTS_BINARY	(	z	,
		z	,
		z
	)

weighted_determinize()

template<typename Aut >

auto awali::sttc::weighted_determinize

(

const Aut &

aut

)

-> mutable_automaton<context_t_of<Aut>>

Weighted determinization of the automaton.

This function only applies to true finite state machine. The result is a deterministic automaton where the weight of the word is given by the final function. If the semiring is not locally finite, the termination is not assured.

Template Parameters

Aut	the type of the automaton

Parameters

aut	the input automaton return a deterministic automaton

weighted_thompson() [1/2]

template<typename Aut , typename Context = context_t_of<Aut>>

Aut awali::sttc::weighted_thompson	(	const Context &	ctx,
		const typename Context::ratexp_t &	exp,
		bool	keep_history = true
	)

builds a variant of the Thompson automaton without epsilon cycles

This automaton is a Thompson-like automaton :

• its shape is similar to a Thompson automaton, with one initial state and one (main) final state;
  
• the number of states is exactly twice the size of the expression and the number of transitions is linear;
  there are at most two outgoing transitions from each state, and if there are two, they are epsilon transitions.

The difference are :

• there is no epsilon-path between the initial and the final state; thus, the initial state may also be final; in this case, this is the only final state distinct from the main one;
  
• there is no epsilon-circuit, thus this automaton is always valid (its behaviour is defined for every input);
  
• its construction involves the computation of the constant term of the expression (and of sub-expressions), thus is the expression is not valid, the construction fails.

This construction is inspired by the ZPC-structure designed in
Jean-Marc Champarnaud, Jean-Luc Ponty, Djelloul Ziadi. From regular expressions to finite automata. Int. J. Comput. Math. 72(4): 415-431 (1999)

Template Parameters

Aut	type of the generated automaton
Context	type of the context of the generated automaton

Parameters

ctx	the context of the automaton to build
exp	the rational expression
keep_history	(optional) if true (default value), the states are stamped with their origin

Returns

the automaton

weighted_thompson() [2/2]

template<typename RatExpSet >

mutable_automaton<sttc::nullable_of<typename RatExpSet::context_t> > awali::sttc::weighted_thompson	(	const RatExpSet &	rs,
		const typename RatExpSet::ratexp_t &	exp,
		bool	keep_history = true
	)

builds a variant of the Thompson automaton without epsilon cycles

Template Parameters

RatExpSet

type of the context of the rational expression

Parameters

rs	the context of the rational expression
exp	the rational expression
keep_history	(optional) if true (default value), the states are stamped with their origin

Returns

the automaton

witness()

template<typename Context >

mutable_automaton<Context> awali::sttc::witness	(	const Context &	ctx,
		unsigned	n
	)

Returns an automaton with n states.

The factory builds an automaton with n states with indices in Z/n Z.
For every state p,

• the first letter of the alphabet labels transitions from p to p+1;
  
• the second letter of the alphabet labels transitions from p to
  
  • 1 if p=0,
  • 0 if p=1,
  • p otherwise;
• the third letter of the alphabet labels transitions from p to
  
  • 0 if p=n -1,
  • p otherwise;
• the other letters do not label any transition.

State 0 is initial, state n-1 is final.

Every transition is created with weight one; thus, if weighted, the automaton realizes the characteristic series of the language described above.

This automaton is the "universal witness" described in
Janusz A. Brzozowski and David Liu, Universal Witnesses for State Complexity of Basic Operations Combined with Reversal,
CIAA 2013, Lecture Notes in Computer Science, vol. 7982, pp. 72-83.
doi : 10.1007/978-3-642-39274-0_8

Template Parameters

Context

the type of the context

Parameters

ctx	the context of the automaton
n	an integer larger than 1

Returns

an automaton with n states

Exceptions

runtime_error

if n is lesser than 2 or if the alphabet has less than 3 letters