Awali
Another Weighted Automata library
Namespaces | Data Structures | Typedefs | Functions
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< 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 ratexpset = variadic_mul_mixin< rat::ratexpset_impl< Context > >
 
template<typename Context >
using ratexpset_of = ratexpset< context< typename labelset_trait< typename Context::labelset_t >::ratlabelset_t, typename Context::weightset_t > >
 
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_taccessible_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_tcoaccessible_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 >
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...
 
template<typename Labelset >
Labelset::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 >
auto get_rat_context (const Context &ctx) -> context< typename labelset_trait< typename Context::labelset_t >::ratlabelset_t, typename Context::weightset_t >
 
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...
 
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<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 >
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 *p)
 
template<unsigned version = version::fsm_json>
json::object_tjson_creator ()
 
template<unsigned version = version::fsm_json>
json::object_tjson_format ()
 
template<unsigned version = version::fsm_json>
json::object_tjson_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)
 
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::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 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)
 
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 &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_tpath_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 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 , 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_treverse_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_tscc_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 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_tuseful_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

◆ awali::sttc::labelset_trait< oneset >

struct awali::sttc::labelset_trait< oneset >

specialisation of labelset_trait for oneset

Data Fields
typedef oneset nullable_t
typedef oneset ratlabelset_t

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

◆ 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< context<typename labelset_trait<typename Context::labelset_t>::ratlabelset_t, typename Context::weightset_t> >

◆ 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
ValueSetthe 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
ValueSetthe 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
AutThe static type of automaton
Parameters
autA static Awali automaton that can be read-only (including view)
keep_historyA 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
AutThe static type of automaton
Parameters
autA 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
AutThe static type of automaton
Parameters
autA static Awali automaton that can be read-only (including view)
include_pre_postif 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
Autthe type of the automaton
Parameters
athe automaton
srcthe source state of the transition
dstthe destination state of the transition
wthe weight of the transition
Returns
the resulting weight of the transition
Exceptions
runtime_errorif 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
Autthe type of the automaton
Parameters
athe automaton
srcthe source state of the transition
dstthe destination state of the transition
Returns
the resulting weight of the transition
Exceptions
runtime_errorif 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
Autthe type of the automaton
Parameters
autthe automaton in which the subautomaton is inserted
pthe source state
qthe destination state
sthe inserted series
strict_alphabetif 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_errorif aut does not allow epsilon-transitions and s is not proper
parse_exceptionif the expression is malformed
domain_errorif 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
Autthe type of the automaton
Parameters
autthe automaton in which the subautomaton is inserted
pthe source state
qthe destination state
expthe inserted series
Exceptions
std::runtime_errorif 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
Autthe type of the input automaton
Parameters
autthe input automaton
keep_historyif 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
Aut1the type of the first automaton
Aut2the type of the second automaton
Parameters
a1the first automaton
a2the 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
Autthe type of the automaton
Contextthe context of rational expressions
Parameters
athe 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
Autthe type of the automaton
Contextthe context of rational expressions
Parameters
athe automaton
next_statean 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
Autthe type of the automaton
Contextthe context of rational expressions
Parameters
athe 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
Autthe type of the automaton
Parameters
autthe automaton
mina non negative integer
maxan 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
RatExpSettype of the value set of the expression
Parameters
rsthe value set of the expression
ra rational expression
mina non negative integer
maxan 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
Autthe type of the automaton
Letterthe type of the letters
Parameters
autthe automaton
lettersa set of letters
del_unvalid_transitionsif 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
AutThe static type of automaton
Parameters
autA static Awali automaton that can be read-only (including view)
keep_historyA 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
AutThe static type of automaton
Parameters
autA 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
AutThe static type of automaton
Parameters
autA static Awali automaton that can be read-only (including view)
include_pre_postif 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
Autthe type of the automaton
Parameters
autthe input automaton
keep_historyif 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
Autthe type of the input automaton
Parameters
autthe automaton
keep_historyif 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
Autthe type of the input automaton
Parameters
autthe 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
Auttype of the generated automaton
Contexttype of the context of the generated automaton
Parameters
ctxthe context of the generated automaton
expthe 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
RatExpSettype of the context of the rational expression
Parameters
rsthe context of the rational expression
expthe 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
Autthe type of the automaton
Parameters
auta Boolean deterministic complete automaton
keep_historyif 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
Autthe type of the automaton
Parameters
auta 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
Autthe type of the automaton
Parameters
auta Boolean deterministic automaton
keep_historyif 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
Autthe type of the automaton
Parameters
auta 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
TDC1the type of the firt transducer
TDC2the type of the second transducer
Parameters
tdc1the first transducer
tdc2the second transducer
keep_historyif 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
Ithe index of the composing tape of the first transducer
Jthe index of the composing tape of the second transducer
TDC1the type of the firt transducer
TDC2the type of the second transducer
Parameters
tdc1the first transducer
tdc2the second transducer
keep_historyif 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
Aut1the type of the first automaton
Aut2the type of the second automaton
Parameters
aut1the first automaton
aut2the 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
ValueSetthe type of a value set
Parameters
vsa value set (ratexpset, weightset, etc.)
lhsa value in the value set
rhsa 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
Athe type of the modified automaton
Bthe type of the added automaton
Parameters
resthe modifed automaton
autthe 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
Autthe type of the automaton
Parameters
autthe 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
Autthe type of the automaton
Parameters
athe automaton
srcthe source state of the transition
dstthe destination state of the transition
Exceptions
runtime_errorif 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
Autthe type of the automaton
Parameters
athe input automaton
keep_historyif 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
aut1an automaton labeled by letters
aut2a 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
Contextthe type of the context
Parameters
ctxthe context of the automaton
divisora positive integer
basea positive integer
Returns
an automaton with divisor states
Exceptions
runtime_errorif 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
Contextthe type of the context
Parameters
ctxthe context of the automaton
na positive integer
finalsa vector of states
Returns
an automaton with n states
Exceptions
runtime_errorif 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
isthe stream to read.
cthe expected character.
Exceptions
std::runtime_errorif 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
isthe stream to read.
expectthe expected string.
Exceptions
std::runtime_errorif 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
Autan 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
Automatontype
Parameters
autthe automaton
max_lengththe 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
Autthe type of the automaton
Tdcthe type of the transducer
Parameters
autthe automaton
tdcthe transducer
keep_historyif 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
RatExpSettype of the context of the rational expression
Parameters
rsthe context of the rational expression
expthe 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.

◆ 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()

template<typename Labelset >
Labelset::value_t awali::sttc::get_epsilon ( )

Helper to get the value of epsilon.

Template Parameters
Labelsetthe label set
Returns
the value of epsilon
Exceptions
runtime_errorif 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 >
auto awali::sttc::get_rat_context ( const Context &  ctx) -> context<typename labelset_trait<typename Context::labelset_t>::ratlabelset_t, typename Context::weightset_t>

◆ 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
Autthe type of the automaton
Parameters
auta Boolean deterministic automaton
states_in_parta 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
Tdcthe type of the transducer
Parameters
ina transducer
keep_historyif 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
AutThe static type of automaton
Parameters
autA 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
AutThe static type of automaton
Parameters
autA 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
Autthe type of the automaton
Parameters
autthe 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
AutThe static type of automaton
Parameters
autA 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()

template<typename Labelset >
bool awali::sttc::is_epsilon ( const typename Labelset::value_t &  l)

Helper to test if a label is epsilon.

Template Parameters
Labelsetthe label set
Parameters
lthe label
Returns
true if the label is epsilon
Exceptions
runtime_errorif the label set does not admit epsilon transitions

◆ 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
Ithe index of the tape
Tdcthe type of transducer
Parameters
tdcthe 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
autThe tested automaton
Returns
true iff the automaton is proper

◆ 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
Autthe type of the automaton
Parameters
autthe 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
autA 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
AutThe static type of automaton
Parameters
autA 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
autThe 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 p 
)

◆ 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
Contextthe type of the context
Parameters
ctxthe context of the automaton
na positive integer
Returns
an automaton with n states
Exceptions
runtime_errorif 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
Autthe type of the automaton
Parameters
resthe automaton
wthe weight
standardif 'true' and res is a standard automaton, applies a standard multiplication
Returns
the automaton res
Exceptions
runtime_errorif 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() [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)

◆ 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
TThe type of the weightset : z, c, zz<5>, ... (must be included)
Parameters
lettersAn 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
TThe type of the weightset : z, c, zz<5>, ... (must be included)
Parameters
lettersAn 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_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 ( e1,
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
Autthe type of the automaton
Parameters
auta Boolean deterministic automaton
states_in_parta 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
Autthe type of the automaton
Parameters
athe automaton
srcthe source state of the transition
dstthe destination state of the transition
wthe 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
Autthe type of the automaton
Parameters
athe automaton
srcthe source state of the transition
dstthe destination state of the transition
Returns
the identifier of the created transition
Exceptions
runtime_errorif 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
AutThe static type of automaton
Parameters
autA 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
AutThe static type of automaton
Parameters
autA 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
AutThe static type of automaton
Parameters
autA 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
filethe 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
filethe file name. "-" and "" denote stdout.

◆ 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 &  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
RatExpSetthe type of the context of rational expressions
Parameters
ratexpsetthe context of rational expressions
sthe expression to parse
check_completeif true, the parsing must encompass the whole string; otherwise, it may apply only to a suffix
strict_alphabetif true every letter must belong to the alphabet in ratexpset, otherwise, it shall be added
Exceptions
parse_exceptionif the expression is malformed
domain_errorif 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
Ithe number of tapes of the result
Autthe type of the automaton
Parameters
inthe automaton
keep_historyif 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
Ithe index of a tape
Tdcthe type of the transducer
Parameters
ina transducer
keep_historyif 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
Ithe list of the indices of tapes
Tdcthe type of the transducer
Parameters
ina transducer
keep_historyif true the result is endowed with a single_history to the input transducer
Returns
a transducer obtained from in with the given tapes

◆ 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_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
Autthe type of the automaton
Letterthe type of the letters
Parameters
autthe automaton
lettersa set of letters
del_unvalid_transitionsif 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
Autthe type of the automaton
Parameters
autthe 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
Autthe type of the automaton
Parameters
autthe automaton
sa 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
Autthe type of the automaton
Parameters
autthe 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
Autthe type of the automaton
Parameters
athe automaton
srcthe source state of the transition
dstthe destination state of the transition
wthe weight of the transition
Returns
the identifier of the created transition
Exceptions
runtime_errorif 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
Autthe type of the automaton
Parameters
athe automaton
srcthe source state of the transition
dstthe destination state of the transition
Returns
the identifier of the created transition
Exceptions
runtime_errorif 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
Autan 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
Aut1the type of the first automaton
Aut2the type of the second automaton
Parameters
aut1the first automaton
aut2the second automaton
sum_standardif true, and aut1 and aut2 are standard automata, the result is standard
Returns
an automaton
Exceptions
runtime_errorif 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
Resthe type of the first automaton
Autthe type of the second automaton
Parameters
resthe first automaton
autthe second automaton
sum_standardif true, and aut1 and aut2 are standard automata, the result is standard
Returns
the automaton res
Exceptions
runtime_errorif 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.

◆ 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
Auttype of the generated automaton
Contexttype of the context of the generated automaton
Parameters
ctxthe context of the generated automaton
expthe 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
RatExpSettype of the context of the rational expression
Parameters
rsthe context of the rational expression
expthe 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
AutPtran 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
AutThe static type of automaton
Parameters
autA static Awali automaton that can be read-only (including view)
keep_historyA 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
AutThe static type of automaton
Parameters
autA 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
AutThe static type of automaton
Parameters
autA static Awali automaton that can be read-only (including view)
include_pre_postif 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
Autthe type of the automaton
Parameters
autthe 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
Auttype of the generated automaton
Contexttype of the context of the generated automaton
Parameters
ctxthe context of the automaton to build
expthe 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
RatExpSettype of the context of the rational expression
Parameters
rsthe context of the rational expression
expthe 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
Contextthe type of the context
Parameters
ctxthe context of the automaton
nan integer larger than 1
Returns
an automaton with n states
Exceptions
runtime_errorif n is lesser than 2 or if the alphabet has less than 3 letters