Files | |
file | accessible.hh |
Algorithms for accessible/coaccessible states computation. | |
file | aci_canonical.hh |
Declaration for the canonical() algorithm. | |
file | aut_to_exp.hh |
This file provides converter from automaton to expression. | |
file | berry_sethi.hh |
Contains the declaration for the Berry-Sethi algorithm. | |
file | brzozowski.hh |
Contains the declaration for the Brzozowski algorithm. | |
file | complement.hh |
Complementation algorithm for Boolean automata. | |
file | complete.hh |
Testing and building complete automata. | |
file | composition_cover.hh |
Composition for normalized and sub-normalized transducers seen as automata over a free monoid product. | |
file | concatenate.hh |
This file provides the general concatenation algorithm. | |
file | derived_term_automaton.hh |
Provides a converter from expression to automaton based on derivatives. | |
file | determinize.hh |
Boolean automata determinization. | |
file | domain.hh |
Domain algorithm. | |
file | eps_removal.hh |
This files declares the backward and forward eps_removal algorithm. | |
file | eps_removal_sp.hh |
This files declares the backward and forward eps_removal algorithm. | |
file | equivalent.hh |
This file contains the declarations for the are_equivalent() algorithm. | |
file | eval.hh |
This file provides the evaluation of a word w.r.t an automaton. | |
file | evaluation_fmp.hh |
Evaluation over normalized and sub-normalized transducers seen as automata over a free monoid product. | |
file | extension.hh |
Declarations for extension(). | |
file | finite_support_conversion.hh |
Conversion between finite support application types. | |
file | fmp_to_rw.hh |
This file provides a transformation function that computes the Rational Weight transducer of a FMP automaton. | |
file | has_succ_comp.hh |
Declaration of has_succ_comp(). | |
file | image.hh |
Image projection for transducers. | |
file | initial_derivation.hh |
Declaration of the initial derivation visitor, used for smart_derivative_automaton. | |
file | evaluation.hh |
Internal functions used by the rw_composition algorithm. | |
file | outsplitting.hh |
Outsplitting and insplitting algorithms for normalized and sub-normalized fmp_transducers. | |
file | is_ambiguous.hh |
Test for ambiguity. | |
file | is_deterministic.hh |
Boolean automata determinization. | |
file | is_empty.hh |
Declaration of is_empty(). | |
file | is_letterized.hh |
Letter-to-letter feature testing. | |
file | is_normalized.hh |
Test for transducer normalization. | |
file | isomorph.hh |
This files contains the declaration for the are_isomorphic() algorithm. | |
file | krat_exp_cderivation.hh |
Declaration for the cderivate() algorithms. | |
file | krat_exp_constant_term.hh |
Declaration for the constant_term() algorithm. | |
file | krat_exp_derivation.hh |
Declaration for the derivate() algorithms. | |
file | krat_exp_expand.hh |
Expand a k-rational-expression. | |
file | krat_exp_flatten.hh |
This file holds the declaration of the flatten() algorithm. | |
file | krat_exp_linearize.hh |
Declarations for the linearize() algorithm. | |
file | krat_exp_partial_derivation.hh |
Declarations for the partial_derivate() algorithm. | |
file | krat_exp_realtime.hh |
Declarations of the realtime() algorithm for rational expressions. | |
file | letter_to_letter_composition.hh |
Undocumented stuff. | |
file | minimization_hopcroft.hh |
This file provides minimization and quotient algorithms. | |
file | minimization_moore.hh |
This file containes the declaration of minimization_moore(). | |
file | normalized.hh |
Thompson normalization operations. | |
file | normalized_composition.hh |
Composition for normalized and sub-normalized transducers seen as automata over a free monoid product. | |
file | product.hh |
Declarations of product(). | |
file | projection.hh |
Undocumented stuff. | |
file | realtime.hh |
General algorithms concerning realtime aspect of automata. | |
file | realtime_decl.hh |
Declaration of the realtime() function. | |
file | rw_composition.hh |
Composition of two Rational-Weight transducers. | |
file | rw_to_fmp.hh |
This file provides a transformation function that computes the equivalent FMP automaton of a Rational Weight tranducer. | |
file | search.hh |
Rational expression search in text. | |
file | standard.hh |
Several algorithms concerning standard automata. | |
file | standard_of.hh |
This file provides a converter from expression to standard automaton. | |
file | sub_automaton.hh |
This file provides the extraction of sub automaton. | |
file | sub_normalize.hh |
Sub-normalization algorithm for FMP transducers. | |
file | sum.hh |
Summing of automata. | |
file | thompson.hh |
The thompson automaton. | |
file | algorithms/transpose.hh |
This file contain the function which transpose an automaton. | |
file | trim.hh |
Declaration of useful_states() and trim(). | |
Classes | |
struct | KRatExpFlatten |
struct | linearize_element |
The types of a linearized expression. More... | |
struct | FindBestSearch |
Specific implementation for search(). More... | |
struct | WindowedBackSearch |
Specific implementation for search(). More... | |
Determinization algorithms | |
template<typename A, typename AI> | |
Element< A, AI > | determinize (const Element< A, AI > &a) |
Build a deterministic automaton from a Boolean automaton. | |
template<typename A, typename AI> | |
Element< A, AI > | determinize (const Element< A, AI > &a, std::map< typename Element< A, AI >::hstate_t, std::set< typename Element< A, AI >::hstate_t > > &m) |
Build a deterministic automaton from a Boolean automaton, keeping trace of state-to-states correspondences. | |
FMP automaton to rational weight transducer algorithm. | |
Compute the equivalent Rational Weight transducer of a FMP automaton. Please note that for the moment this function works only if the support of each transition is finite.
Algorithm : If the FMP contains transitions with "complex" expression (E), i.e. infinite support, then Thompson of E. With the resulting automaton apply a conversion. i.e. (a,x) -> a|x | |
template<typename S, typename T, typename SS, typename TT> | |
Element< SS, TT > & | fmp_to_rw (const Element< S, T > &fmp, Element< SS, TT > &res) |
Product algorithm | |
Returns a fresh automaton that is the product of the two input ones.
| |
template<typename A, typename T, typename U> | |
Element< A, T > | product (const Element< A, T > &lhs, const Element< A, U > &rhs, const bool use_geometry=false) |
template<typename A, typename T, typename U> | |
Element< A, T > | product (const Element< A, T > &lhs, const Element< A, U > &rhs, std::map< typename T::hstate_t, std::pair< typename T::hstate_t, typename U::hstate_t > > &, const bool use_geometry=false) |
Rational Weight transducer to FMP automaton conversion | |
template<typename S, typename T, typename SS, typename TT> | |
Element< SS, TT > & | rw_to_fmp (const Element< S, T > &trans, Element< SS, TT > &res) |
Compute the equivalent FMP automaton of a Rational Weight transducer. | |
Functions | |
template<typename A, typename AI> | |
std::set< typename Element< A, AI >::hstate_t > | accessible_states (const Element< A, AI > &a) |
Return accessible states. | |
template<typename A, typename AI> | |
Element< A, AI > | accessible (const Element< A, AI > &a) |
Extract the sub-automaton composed of accessible states. | |
template<typename A, typename AI> | |
void | accessible_here (Element< A, AI > &a) |
In-place extract the sub-automaton of accessible states. | |
template<typename A, typename AI> | |
std::set< typename Element< A, AI >::hstate_t > | coaccessible_states (const Element< A, AI > &a) |
Return co-accessible states. | |
template<typename A, typename AI> | |
Element< A, AI > | coaccessible (const Element< A, AI > &a) |
Extract the sub-automaton composed of co-accessible states. | |
template<typename A, typename AI> | |
void | coaccessible_here (Element< A, AI > &a) |
In-place extract the sub-automaton of co-accessible states. | |
template<typename S, typename SI> | |
Element< S, SI > | canonical (const Element< S, SI > &exp) |
Transform a krat expression into its canonical form, following aci-rules. | |
template<typename A, typename AI> | |
Element< A, AI >::series_set_elt_t | aut_to_exp (const Element< A, AI > &a) |
Returns a series which describes the language of the automaton. | |
template<typename A, typename AI, typename Chooser> | |
Element< A, AI >::series_set_elt_t | aut_to_exp (const Element< A, AI > &a, const Chooser &c) |
Returns a series which describes the language of the automaton. | |
template<typename A, typename T, typename Exp> | |
void | berry_sethi (Element< A, T > &, const Exp &) |
Build an automaton from an expression using the Berry-Sethi construction. | |
template<typename A, typename T, typename Exp> | |
void | brzozowski (Element< A, T > &, const Exp &) |
Build an automaton from an expression using the Brzozowski construction. | |
template<typename A, typename AI> | |
void | complement_here (Element< A, AI > &a) |
Complement in place the set of final states. | |
template<typename A, typename AI> | |
Element< A, AI > | complement (const Element< A, AI > &a) |
Complement the set of final states. | |
template<typename A, typename AI> | |
void | complete_here (Element< A, AI > &a) |
Make the transition function of an automaton total w.r.t. | |
template<typename A, typename AI> | |
Element< A, AI > | complete (const Element< A, AI > &a) |
Make the transition function of an automaton total w.r.t. | |
template<typename A, typename AI> | |
bool | is_complete (const Element< A, AI > &a) |
Test whether an automaton is complete. | |
template<typename S, typename T> | |
Element< S, T > | composition_cover (const Element< S, T > &fmp) |
Facade for composition cover. | |
template<typename S, typename T> | |
Element< S, T > | composition_co_cover (const Element< S, T > &fmp) |
Facade for composition co-cover. | |
template<typename A, typename AI> | |
Element< A, AI > | concatenate (const Element< A, AI > &lhs, const Element< A, AI > &rhs) |
Return the concatenation of two automata. | |
template<typename A, typename AI> | |
void | concatenate_here (Element< A, AI > &lhs, const Element< A, AI > &rhs) |
In place concatenation of two automata. | |
template<typename A, typename T, typename Exp> | |
void | derived_term_automaton (Element< A, T > &a, const Exp &e) |
Convert a krat expression into an automaton using derivatives. | |
template<typename A, typename T, typename Exp> | |
Element< A, T > | derived_term_automaton (const Exp &e) |
Convert a krat expression into an automaton using derivatives. | |
template<typename A, typename T, typename Exp> | |
Element< A, T > | broken_derived_term_automaton (const Exp &e) |
Convert a krat expression into an automaton using derivatives. | |
template<typename A, typename AI> | |
void | eps_removal_here (Element< A, AI > &a, misc::direction_type dir=misc::backward) |
In place eps_removal of an automaton (default is backward eps_removal). | |
template<typename A, typename AI> | |
Element< A, AI > | eps_removal (const Element< A, AI > &a, misc::direction_type dir=misc::backward) |
Eps_Removal of an automaton (default is backward eps_removal). | |
template<typename A, typename AI> | |
void | backward_eps_removal_here (Element< A, AI > &a) |
In place backward eps_removal of an automaton. | |
template<typename A, typename AI> | |
Element< A, AI > | backward_eps_removal (const Element< A, AI > &a) |
Backward eps_removal of an automaton. | |
template<typename A, typename AI> | |
void | forward_eps_removal_here (Element< A, AI > &a) |
In place forward eps_removal of an automaton. | |
template<typename A, typename AI> | |
Element< A, AI > | forward_eps_removal (const Element< A, AI > &a) |
Forward eps_removal of an automaton. | |
template<typename A, typename AI> | |
void | eps_removal_here_sp (Element< A, AI > &a, misc::direction_type dir=misc::backward) |
In place eps_removal_sp of an automaton (default is backward eps_removal). | |
template<typename A, typename AI> | |
Element< A, AI > | eps_removal_sp (const Element< A, AI > &a, misc::direction_type dir=misc::backward) |
Eps_Removal of an automaton (default is backward eps_removal). | |
template<typename A, typename AI> | |
void | backward_eps_removal_here_sp (Element< A, AI > &a) |
In place backward eps_removal_sp of an automaton. | |
template<typename A, typename AI> | |
Element< A, AI > | backward_eps_removal_sp (const Element< A, AI > &a) |
Backward eps_removal_sp of an automaton. | |
template<typename A, typename AI> | |
void | forward_eps_removal_here_sp (Element< A, AI > &a) |
In place forward eps_removal_sp of an automaton. | |
template<typename A, typename AI> | |
Element< A, AI > | forward_eps_removal_sp (const Element< A, AI > &a) |
Forward eps_removal_sp of an automaton. | |
template<typename S, typename A, typename B> | |
bool | are_equivalent (const Element< S, A > &a, const Element< S, B > &b) |
Returns true iff the two boolean automata are equivalents, i.e., if they recognize the same language. | |
template<typename A, typename AI, typename W> | |
Element< A, AI >::semiring_elt_t | eval (const Element< A, AI > &a, const W &word) |
Return the image of a word by an automaton. | |
template<typename SA, typename TA, typename ST, typename TT, typename SARET, typename TARET> | |
void | evaluation_fmp (const Element< ST, TT > &, const Element< SA, TA > &, Element< SARET, TARET > &) |
Evaluation over normalized and sub-normalized transducers, seen as automata over a free monoid product. | |
template<typename S, typename T> | |
identity_transducer_helper< S, T >::ret | extension (const Element< S, T > &) |
Extend an automaton to a transducer. | |
template<typename SA, typename TA, typename ST, typename TT> | |
Element< ST, TT > | extension (const Element< SA, TA > &, const Element< ST, TT > &) |
Extend an automaton to a transducer. | |
template<typename S, typename T, typename Ss, typename Ts> | |
void | finite_support_convert (Element< S, T > &dst, const Element< Ss, Ts > &org) |
Finite support conversion. | |
template<typename A, typename AI> | |
bool | has_succ_comp (const Element< A, AI > &a) |
Return true if the automaton has successful computation. | |
template<typename SA, typename TA, typename ST, typename TT, typename SARET, typename TARET> | |
void | evaluation (const Element< SA, TA > &a, const Element< ST, TT > &t, Element< SARET, TARET > &ret) |
Evaluate for a "letterized" automaton and a realtime transducer. | |
template<typename SA, typename TA, typename M> | |
void | partial_elimination (const Element< SA, TA > &a, M &state_exp_pair) |
This function computes a set of expression, after having eliminated all states which are not initial or final. | |
template<typename S1, typename T1, typename S2, typename T2, typename M> | |
void | partial_evaluation (const Element< S1, T1 > &E, const Element< S2, T2 > &S, const typename Element< S2, T2 >::hstate_t &p, M &res) |
This function computes a set of expression according to the rw_composition algorithm description. | |
template<typename A, typename AI> | |
bool | is_ambiguous (const Element< A, AI > &aut) |
Test the ambiguity of automaton. | |
template<typename A, typename AI> | |
bool | is_deterministic (const Element< A, AI > &a) |
Test if an automaton is deterministic. | |
template<typename A, typename AI> | |
bool | is_empty (const Element< A, AI > &a) |
Return true if the automaton is empty (has no state), false otherwise. | |
template<typename S, typename A> | |
bool | is_letterized_transducer (const Element< S, A > &t) |
Test the letter to letter features. | |
template<typename S, typename A> | |
bool | is_normalized_transducer (const Element< S, A > &t) |
Test the normalization of transducer. | |
template<typename A, typename T> | |
bool | are_isomorphic (const Element< A, T > &a, const Element< A, T > &b) |
Returns true if the two automata are isomorphic. | |
template<class Series, class T, class Letter> | |
Element< Series, T > | cderivate (const Element< Series, T > &exp, Letter a) |
The c-derivative of the krat expression w.r.t to a letter. | |
template<class Series, class T, class Word> | |
Element< Series, T > | word_cderivate (const Element< Series, T > &exp, Word a) |
The c-derivative of the krat expression w.r.t to a word. | |
template<class Series, class T> | |
std::pair< typename Element < Series, T >::semiring_elt_t, bool > | constant_term (const Element< Series, T > &exp) |
Return the constant term of the krat expression. | |
template<class Series, class T, class Letter> | |
std::pair< Element< Series, T > , bool > | derivate (const Element< Series, T > &exp, Letter a) |
The antimirov derivative of the krat expression w.r.t to a letter. | |
template<class Series, class T, class Word> | |
std::pair< Element< Series, T > , bool > | word_derivate (const Element< Series, T > &exp, Word a) |
The antimirov derivative of the krat expression w.r.t to a word. | |
template<class Series, class T> | |
std::list< typename Series::monoid_t::alphabet_t::letter_t > | flatten (const Element< Series, T > &exp) |
This algorithm extracts the letters from a rational expression. | |
template<class Series, class T> | |
linearize_element< Series, T > ::element_t | linearize (const Element< Series, T > &exp) |
The linearization of the krat expression. | |
template<class Series, class T, class Letter> | |
std::pair< std::set< Element < Series, T > >, bool > | partial_derivate (const Element< Series, T > &exp, Letter a) |
The partial derivative of the krat expression w.r.t to a letter. | |
template<class S, class T> | |
Element< S, T > | letter_to_letter_composition (const Element< S, T > &lhs, const Element< S, T > &rhs) |
Undocumented. | |
template<typename A, typename AI> | |
Element< A, AI > | minimization_hopcroft (const Element< A, AI > &a) |
Return the minimal automaton using the hopcroft algorithm. | |
template<typename A, typename AI> | |
Element< A, AI > | quotient (const Element< A, AI > &a) |
Return the quotient of a non-deterministic acceptor. | |
template<typename A, typename AI> | |
Element< A, AI > | minimization_moore (const Element< A, AI > &a) |
Returns the minimal deterministic automaton associated to the input one. | |
template<typename A, typename AI> | |
Element< A, AI > | co_minimization_moore (const Element< A, AI > &a) |
Returns the co-minimal co-deterministic automaton associated to the input one. | |
template<typename A, typename AI> | |
void | minimization_moore_here (Element< A, AI > &a) |
Minimalize the deterministic input automaton. | |
template<typename A, typename AI> | |
void | co_minimization_moore_here (Element< A, AI > &a) |
Co-minimalize the co-deterministic input automaton. | |
template<typename A, typename AI> | |
Element< A, AI > | normalize (const Element< A, AI > &a) |
Return the fresh thompson-normalized automaton. | |
template<typename A, typename AI> | |
void | normalize_here (Element< A, AI > &a) |
In-place normalize to the thompson form. | |
template<typename A, typename AI> | |
bool | is_normalized (const Element< A, AI > &a) |
Return true if the input automaton is thompson-normalized. | |
template<typename A, typename AI1, typename AI2> | |
void | union_of_normalized_here (Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
Do the in-place union of two thompson-normalized automata. | |
template<typename A, typename AI1, typename AI2> | |
Element< A, AI1 > | union_of_normalized (const Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
Return the fresh union of two thompson-normalized automata. | |
template<typename A, typename AI1, typename AI2> | |
void | concatenate_of_normalized_here (Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
Do the in-place concatenation of two thompson-normalized automata. | |
template<typename A, typename AI1, typename AI2> | |
Element< A, AI1 > | concatenate_of_normalized (const Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
Return the fresh concatenation of two thompson-normalized automata. | |
template<typename A, typename AI> | |
void | star_of_normalized_here (Element< A, AI > &a) |
Do in-place star transformation on the thompson-normalized input. | |
template<typename A, typename AI> | |
Element< A, AI > | star_of_normalized (const Element< A, AI > &a) |
Return the fresh star transformation of its normalized input. | |
template<typename S, typename T> | |
void | compose (const Element< S, T > &lhs, const Element< S, T > &rhs, Element< S, T > &ret) |
Composition for weighted normalized and sub-normalized transducers, seen as automata over a free monoid product. | |
template<typename S, typename T> | |
Element< S, T > | compose (const Element< S, T > &lhs, const Element< S, T > &rhs) |
Composition for weighted normalized and sub-normalized transducers, seen as automata over a free monoid product. | |
template<typename S, typename T> | |
void | u_compose (const Element< S, T > &lhs, const Element< S, T > &rhs, Element< S, T > &ret) |
Unambiguous composition for weighted normalized and sub-normalized transducers, seen as automata over a free monoid product. | |
template<typename S, typename T> | |
Element< S, T > | u_compose (const Element< S, T > &lhs, const Element< S, T > &rhs) |
Unambiguous composition for weighted normalized and sub-normalized transducers, seen as automata over a free monoid product. | |
template<typename auto_t, typename trans_t> | |
void | set_states (const trans_t &, auto_t &, std::map< typename trans_t::hstate_t, typename auto_t::hstate_t > &) |
template<typename A, typename AI> | |
void | realtime_here (Element< A, AI > &a, misc::direction_type dir) |
Modify an automaton in place to make it realtime. | |
template<typename A, typename AI> | |
Element< A, AI > | realtime (const Element< A, AI > &a, misc::direction_type dir) |
Create a realtime automaton from another one. | |
template<typename S, typename T> | |
Element< S, T > | realtime (const Element< S, T > &e) |
Compute the realtime version of a rational expression or an automata. | |
template<typename S, typename T> | |
void | realtime_here (Element< S, T > &e) |
Modify a rational expression or automata in place to make it realtime. | |
template<typename S, typename T> | |
bool | is_realtime (const Element< S, T > &e) |
Test whether an automaton or a rational expression is realtime. | |
template<typename S, typename T> | |
void | rw_composition (const Element< S, T > &, const Element< S, T > &, Element< S, T > &) |
Composition for Rational-Weight transducers. | |
template<typename S, typename T> | |
Element< S, T > | rw_composition (const Element< S, T > &, const Element< S, T > &) |
Composition for Rational-Weight transducers. | |
template<class InputIterator, class FoundFunctor, class Series, class T> | |
void | search (const Element< Automata< Series >, T > &a, const InputIterator &begin, const InputIterator &end, typename Element< Automata< Series >, T >::letter_t eol, FoundFunctor &f) |
Search for a rational expression into a text. | |
template<class Series, class T, class StatesSet> | |
static unsigned int | compute_distances (const Element< Automata< Series >, T > &a, std::vector< StatesSet > &distances) |
Compute distances from initial states to final states. | |
template<class InputIterator, class Series, class T, class StatesSet> | |
static std::pair< bool, unsigned int > | window_backsearch (const misc::Window< InputIterator, typename Element< Automata< Series >, T >::letter_t > &w, const Element< Automata< Series >, T > &a, const std::vector< StatesSet > &distances) |
Back search inside a window. | |
template<class InputIterator, class FoundFunctor, class Series, class T> | |
static InputIterator | confirm_and_report_match (const misc::Window< InputIterator, typename Element< Automata< Series >, T >::letter_t > &w, const Element< Automata< Series >, T > &a, FoundFunctor &f) |
Finds the longest match of a starting from w, and report it to the functor. | |
template<typename A, typename AI> | |
void | standardize (Element< A, AI > &a) |
Returns a standard automaton associated to the input. | |
template<typename A, typename AI> | |
bool | is_standard (const Element< A, AI > &a) |
Returns true if the input automaton is standard. | |
template<typename A, typename AI1, typename AI2> | |
void | union_of_standard_here (Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
In-place union of two standard automata. | |
template<typename A, typename AI1, typename AI2> | |
Element< A, AI1 > | union_of_standard (const Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
Return a fresh union of two standard automata. | |
template<typename A, typename AI1, typename AI2> | |
void | concat_of_standard_here (Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
In-place concatenation of two standard automata. | |
template<typename A, typename AI1, typename AI2> | |
Element< A, AI1 > | concat_of_standard (const Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
Return a fresh concatenation of two standard automata. | |
template<typename A, typename AI> | |
void | star_of_standard_here (Element< A, AI > &a) |
In-place star transformation of a standard automata. | |
template<typename A, typename AI> | |
Element< A, AI > | star_of_standard (const Element< A, AI > &a) |
Return the fresh star transformation of a standard automata. | |
template<typename A, typename T, typename Exp> | |
void | standard_of (Element< A, T > &a, const Exp &e) |
Convert a rational expression into a standard automaton. | |
template<typename A, typename AI, typename HStatesSet> | |
Element< A, AI > | sub_automaton (const Element< A, AI > &a, const HStatesSet &s, bool check_states=true) |
Returns a fresh automaton that is the sub-automaton defined by a set. | |
template<typename A, typename AI, typename HStatesSet> | |
void | sub_automaton_here (Element< A, AI > &a, const HStatesSet &s, bool check_states=true) |
Select a sub-automaton into a given automaton. | |
template<class S, class T> | |
Element< S, T > | sub_normalize (const Element< S, T > &a) |
Sub-normalize a FMP transducer. | |
template<class S, class T1, class T2> | |
void | sub_normalize (const Element< S, T1 > &a, Element< S, T2 > &res) |
Sub-normalize a FMP transducer. | |
template<class S, class T> | |
void | sub_normalize_here (Element< S, T > &a) |
Sub-normalize a FMP transducer, in place version. | |
template<class S, class T> | |
bool | is_sub_normalized (const Element< S, T > &a) |
Check if a FMP transducer is sub-normalized. | |
template<typename A, typename AI1, typename AI2> | |
void | sum_here (Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
In place summing of two automata. | |
template<typename A, typename AI1, typename AI2> | |
Element< A, AI1 > | sum (const Element< A, AI1 > &lhs, const Element< A, AI2 > &rhs) |
Summing of two automata. | |
template<typename A, typename T, typename Letter, typename Weight> | |
void | thompson_of (Element< A, T > &out, const rat::exp< Letter, Weight > &kexp) |
The Thompson automaton associated to the krat expression. | |
template<class AutoType, class S, class T> | |
Element< Automata< S >, AutoType > | thompson_of (const Element< S, T > &exp) |
The Thompson automaton associated to the krat expression. | |
template<typename A, typename AI1, typename AI2> | |
void | transpose (Element< A, AI1 > &dst, const Element< A, AI2 > &from) |
Transposition of an automaton. | |
template<typename A, typename AI> | |
Element< A, AI > | transpose (const Element< A, AI > &from) |
Return a fresh transposed automaton. | |
template<typename A, typename AI> | |
std::set< typename Element< A, AI >::hstate_t > | useful_states (const Element< A, AI > &a) |
Returns a useful states of the automaton. | |
template<typename A, typename AI> | |
Element< A, AI > | trim (const Element< A, AI > &a) |
Return a fresh automaton in which non useful states are removed. | |
template<typename A, typename AI> | |
void | trim_here (Element< A, AI > &a) |
Trim a. |
std::set< typename Element< A, AI >::hstate_t > accessible_states | ( | const Element< A, AI > & | a | ) | [inline] |
Return accessible states.
This functions returns the accessible states set of its input automaton.
a | The input automaton. |
Definition at line 82 of file accessible.hxx.
References Element::structure().
Referenced by vcsn::accessible(), and vcsn::accessible_here().
Element< A, AI > accessible | ( | const Element< A, AI > & | a | ) | [inline] |
Extract the sub-automaton composed of accessible states.
This function returns a fresh sub-automaton of its input containing only accessible states.
a | The input automaton. |
Definition at line 97 of file accessible.hxx.
References vcsn::accessible_states(), and vcsn::sub_automaton().
void accessible_here | ( | Element< A, AI > & | a | ) | [inline] |
In-place extract the sub-automaton of accessible states.
This function computes the sub-autmaton of accessible states from its input automaton. The operation is performed in-place.
a | An in/out parameter which contains the automaton to work on as input and the result as output. |
Definition at line 90 of file accessible.hxx.
References vcsn::accessible_states(), and vcsn::sub_automaton_here().
std::set< typename Element< A, AI >::hstate_t > coaccessible_states | ( | const Element< A, AI > & | a | ) | [inline] |
Return co-accessible states.
This functions returns the co-accessible states set of its input automaton, i.e. states which are accessible from final states.
a | The input automaton. |
Definition at line 116 of file accessible.hxx.
References Element::structure().
Referenced by vcsn::coaccessible(), and vcsn::coaccessible_here().
Element< A, AI > coaccessible | ( | const Element< A, AI > & | a | ) | [inline] |
Extract the sub-automaton composed of co-accessible states.
This function returns a fresh sub-automaton of its input containing only co-accessible states, i.e. states which are accessible from final states.
a | The input automaton. |
Definition at line 123 of file accessible.hxx.
References vcsn::coaccessible_states(), and vcsn::sub_automaton().
void coaccessible_here | ( | Element< A, AI > & | a | ) | [inline] |
In-place extract the sub-automaton of co-accessible states.
This function computes the sub-autmaton of co-accessible states from its input automaton. The operation is performed in-place.
a | An in/out parameter which contains the automaton to work on as input and the result as output. |
Definition at line 130 of file accessible.hxx.
References vcsn::coaccessible_states(), and vcsn::sub_automaton_here().
Element< S, SI > canonical | ( | const Element< S, SI > & | exp | ) | [inline] |
Transform a krat expression into its canonical form, following aci-rules.
exp | The input krat expression. |
Definition at line 181 of file aci_canonical.hxx.
References Element::structure().
Referenced by BrzozowskiAlgo::on_state().
Element< A, AI >::series_set_elt_t aut_to_exp | ( | const Element< A, AI > & | a | ) | [inline] |
Returns a series which describes the language of the automaton.
This algorithm works on every kind of series. However, if, during the computation, it must take the star of it, it can fail. By passing a "generalized" automaton, that is an automaton with rational expression as label, you will be sure to have the algorithm succeed since we can always take the star of a rational expression.
a | The automaton to convert. |
Definition at line 364 of file aut_to_exp.hxx.
Element< A, AI >::series_set_elt_t aut_to_exp | ( | const Element< A, AI > & | a, | |
const Chooser & | c | |||
) | [inline] |
Returns a series which describes the language of the automaton.
This algorithm works on every kind of series. However, if, during the computation, it must take the star of it, it can fail. By passing a "generalized" automaton, that is an automaton with rational expression as label, you will be sure to have the algorithm succeed since we can always take the star of a rational expression.
a | The automaton to work on. | |
c | An object-function that returns the next state to remove from the current state and the automaton. |
Definition at line 355 of file aut_to_exp.hxx.
References Element::structure().
void complement_here | ( | Element< A, AI > & | a | ) | [inline] |
Complement in place the set of final states.
a | The deterministic Boolean automaton to complement. |
a must be deterministic.
Definition at line 38 of file complement.hxx.
References vcsn::is_complete(), and vcsn::is_deterministic().
Referenced by vcsn::complement().
Element< A, AI > complement | ( | const Element< A, AI > & | a | ) | [inline] |
Complement the set of final states.
a | the deterministic Boolean automaton to complement. |
a must be deterministic.
Definition at line 59 of file complement.hxx.
References vcsn::complement_here().
void complete_here | ( | Element< A, AI > & | a | ) | [inline] |
Make the transition function of an automaton total w.r.t.
the alphabet.
See is_complete() for the definition of a complete automaton.
a | the automaton to complete. |
Definition at line 40 of file complete.hxx.
References vcsn::is_realtime(), and Element::structure().
Referenced by vcsn::complete().
Element< A, AI > complete | ( | const Element< A, AI > & | a | ) | [inline] |
Make the transition function of an automaton total w.r.t.
the alphabet.
See is_complete() for the definition of a complete automaton.
a | the automaton to complete. |
Definition at line 85 of file complete.hxx.
References vcsn::complete_here().
bool is_complete | ( | const Element< A, AI > & | a | ) | [inline] |
Test whether an automaton is complete.
An automaton over a free-monoid is complete if each letter of the alphabet can be read from any of its state (i.e., for each state s
and each letter l
, there is at least one outgoing transition labeled by s
), and if there is at least one initial state.
The above definition will also work with non-boolean automata.
a | automaton to test. |
Definition at line 98 of file complete.hxx.
References vcsn::is_realtime(), and Element::structure().
Referenced by vcsn::co_minimization_moore(), vcsn::co_minimization_moore_here(), vcsn::complement_here(), vcsn::minimization_hopcroft(), vcsn::minimization_moore(), and vcsn::minimization_moore_here().
Element<S, T> vcsn::composition_cover | ( | const Element< S, T > & | fmp | ) | [inline] |
Facade for composition cover.
Element< A, AI > concatenate | ( | const Element< A, AI > & | lhs, | |
const Element< A, AI > & | rhs | |||
) | [inline] |
Return the concatenation of two automata.
This function produces a new automata that realizes L(lhs).L(rhs).
lhs | The first automaton. | |
rhs | The second automaton. |
Definition at line 61 of file concatenate.hxx.
References Element::structure().
void concatenate_here | ( | Element< A, AI > & | lhs, | |
const Element< A, AI > & | rhs | |||
) | [inline] |
In place concatenation of two automata.
This function modifies lhs to concatenate the language L(rhs) to its language.
It returns the concatenation of two automata using epsilon transitions.
lhs | The first automaton. | |
rhs | The second automaton. |
Definition at line 70 of file concatenate.hxx.
References Element::structure().
void derived_term_automaton | ( | Element< A, T > & | a, | |
const Exp & | e | |||
) | [inline] |
Convert a krat expression into an automaton using derivatives.
This algorithm produces an automaton from an expression using the Brzozowski construction. This construction involves multiple derivations on the initial expression.
a | An automaton to store the results. | |
e | The expression to convert. |
Definition at line 164 of file derived_term_automaton.hxx.
Referenced by vcsn::derived_term_automaton().
Element< A, T > derived_term_automaton | ( | const Exp & | e | ) | [inline] |
Convert a krat expression into an automaton using derivatives.
e | The expression to convert. |
Definition at line 174 of file derived_term_automaton.hxx.
References vcsn::derived_term_automaton().
Element< A, T > broken_derived_term_automaton | ( | const Exp & | e | ) | [inline] |
Convert a krat expression into an automaton using derivatives.
Derivations are first performed on the starting expression with the following formulae: d(0)={0}, d(1)={1}, d(a)={a} for all a in the alphabet, d(E+F)=d(E) union d(F), d(E.F)=[d(E)].F, d(E*)={E*}
e | The expression to convert. |
Definition at line 215 of file derived_term_automaton.hxx.
Element< A, AI > determinize | ( | const Element< A, AI > & | a | ) | [inline] |
Build a deterministic automaton from a Boolean automaton.
This function build a complete and deterministic automaton using the so called "subset construction".
a | The Boolean automaton to determinize. |
a must be a realtime automaton.
Definition at line 186 of file determinize.hxx.
Element< A, AI > determinize | ( | const Element< A, AI > & | a, | |
std::map< typename Element< A, AI >::hstate_t, std::set< typename Element< A, AI >::hstate_t > > & | m | |||
) | [inline] |
Build a deterministic automaton from a Boolean automaton, keeping trace of state-to-states correspondences.
This function build a complete and deterministic automaton using the so called "subset construction" but also returns the map associating each state of the new automaton to the corresponding subset of states from the original automaton.
a | The Boolean automaton to determinize. | |
m | A map which will be augmented with the correspondance from one state of the resulting automaton to a subset of states of the input automaton. |
a must be a realtime automaton.
Definition at line 175 of file determinize.hxx.
References Element::structure().
void eps_removal_here | ( | Element< A, AI > & | a, | |
misc::direction_type | dir = misc::backward | |||
) | [inline] |
In place eps_removal of an automaton (default is backward eps_removal).
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the Floyd/McNaughton/Yamada algorithm.
a | The weighted automaton to close. | |
dir | The orientation of the eps_removal. |
Definition at line 432 of file eps_removal.hxx.
References SELECT, and Element::structure().
Referenced by vcsn::do_u_compose().
Element< A, AI > eps_removal | ( | const Element< A, AI > & | a, | |
misc::direction_type | dir = misc::backward | |||
) | [inline] |
Eps_Removal of an automaton (default is backward eps_removal).
This algorithm completes the given automaton into a copy to make it close over epsilon transition.
It is based on the Floyd/McNaughton/Yamada algorithm.
a | The weighted automaton to close. | |
dir | The orientation of the eps_removal. |
Definition at line 444 of file eps_removal.hxx.
References SELECT.
void backward_eps_removal_here | ( | Element< A, AI > & | a | ) | [inline] |
In place backward eps_removal of an automaton.
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the Floyd/McNaughton/Yamada algorithm.
a | The weighted automaton to close. |
Definition at line 458 of file eps_removal.hxx.
References SELECT, and Element::structure().
Element< A, AI > backward_eps_removal | ( | const Element< A, AI > & | a | ) | [inline] |
Backward eps_removal of an automaton.
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the Floyd/McNaughton/Yamada algorithm.
a | The weighted automaton to close. |
Definition at line 470 of file eps_removal.hxx.
References SELECT.
void forward_eps_removal_here | ( | Element< A, AI > & | a | ) | [inline] |
In place forward eps_removal of an automaton.
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the Floyd/McNaughton/Yamada algorithm.
a | The weighted automaton to close. |
Definition at line 484 of file eps_removal.hxx.
References SELECT, and Element::structure().
Element< A, AI > forward_eps_removal | ( | const Element< A, AI > & | a | ) | [inline] |
Forward eps_removal of an automaton.
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the Floyd/McNaughton/Yamada algorithm.
a | The weighted automaton to close. |
Definition at line 496 of file eps_removal.hxx.
References SELECT.
void eps_removal_here_sp | ( | Element< A, AI > & | a, | |
misc::direction_type | dir = misc::backward | |||
) | [inline] |
In place eps_removal_sp of an automaton (default is backward eps_removal).
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the shortest-path algorithm.
a | The weighted automaton to close. | |
dir | The orientation of the eps_removal. |
Definition at line 367 of file eps_removal_sp.hxx.
References SELECT, and Element::structure().
Element< A, AI > eps_removal_sp | ( | const Element< A, AI > & | a, | |
misc::direction_type | dir = misc::backward | |||
) | [inline] |
Eps_Removal of an automaton (default is backward eps_removal).
This algorithm completes the given automaton into a copy to make it close over epsilon transition.
It is based on the shortest-path algorithm.
a | The weighted automaton to close. | |
dir | The orientation of the eps_removal. |
Definition at line 379 of file eps_removal_sp.hxx.
References SELECT.
void backward_eps_removal_here_sp | ( | Element< A, AI > & | a | ) | [inline] |
In place backward eps_removal_sp of an automaton.
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the shortest-path algorithm.
a | The weighted automaton to close. |
Definition at line 393 of file eps_removal_sp.hxx.
References SELECT, and Element::structure().
Element< A, AI > backward_eps_removal_sp | ( | const Element< A, AI > & | a | ) | [inline] |
Backward eps_removal_sp of an automaton.
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the shortest-path algorithm.
a | The weighted automaton to close. |
Definition at line 405 of file eps_removal_sp.hxx.
References SELECT.
void forward_eps_removal_here_sp | ( | Element< A, AI > & | a | ) | [inline] |
In place forward eps_removal_sp of an automaton.
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the shortest-path algorithm.
a | The weighted automaton to close. |
Definition at line 419 of file eps_removal_sp.hxx.
References SELECT, and Element::structure().
Element< A, AI > forward_eps_removal_sp | ( | const Element< A, AI > & | a | ) | [inline] |
Forward eps_removal_sp of an automaton.
This algorithm completes in place the given automaton to make it close over epsilon transition.
It is based on the shortest-path algorithm.
a | The weighted automaton to close. |
Definition at line 431 of file eps_removal_sp.hxx.
References SELECT.
bool are_equivalent | ( | const Element< S, A > & | a, | |
const Element< S, B > & | b | |||
) | [inline] |
Returns true iff the two boolean automata are equivalents, i.e., if they recognize the same language.
Definition at line 75 of file equivalent.hxx.
References Element::structure().
Element< A, AI >::semiring_elt_t eval | ( | const Element< A, AI > & | a, | |
const W & | word | |||
) | [inline] |
Return the image of a word by an automaton.
eval(a, w) returns a series that is the image of the word 'w' in the automaton. This version of computation is the most general one : it works on every types of automaton, deterministic or not. Yet, the automaton must be realtime.
Definition at line 105 of file eval.hxx.
References Element::structure().
identity_transducer_helper<S, T>::ret vcsn::extension | ( | const Element< S, T > & | a | ) | [inline] |
Extend an automaton to a transducer.
Extend an automaton to a transducer whose multiplicity is the series of the automaton.
Element< ST, TT > extension | ( | const Element< SA, TA > & | a, | |
const Element< ST, TT > & | t | |||
) | [inline] |
Extend an automaton to a transducer.
Extend an automaton to a transducer whose set is the one of another transducer passed in the second argument. This extension is required if we want to make a product of an automaton with a transducer. If this is not the case, we need simply call extension(automaton_t) above.
Definition at line 205 of file extension.hxx.
References Element::structure().
void vcsn::finite_support_convert | ( | Element< S, T > & | dst, | |
const Element< Ss, Ts > & | org | |||
) | [inline] |
Finite support conversion.
This algorithm copies the value of a finite support application to another, possibly changing its type.
org | The source application to convert. | |
dst | The destination application. |
bool has_succ_comp | ( | const Element< A, AI > & | a | ) | [inline] |
Return true if the automaton has successful computation.
Return true if the automaton has successful computation, false otherwise. Having a successful complete means to have at least one state that is both accessible and co-accessible.
a | The input automaton. |
Definition at line 31 of file has_succ_comp.hxx.
References vcsn::trim().
void vcsn::evaluation | ( | const Element< SA, TA > & | a, | |
const Element< ST, TT > & | t, | |||
Element< SARET, TARET > & | ret | |||
) | [inline] |
Evaluate for a "letterized" automaton and a realtime transducer.
a | lhs | |
t | rhs | |
ret | the result of the evaluation |
void vcsn::partial_elimination | ( | const Element< SA, TA > & | a, | |
M & | state_exp_pair | |||
) | [inline] |
This function computes a set of expression, after having eliminated all states which are not initial or final.
a | input automaton | |
state_exp_pair | the output mapping | |
state_exp_pair | a mapping from the final to the expression of the label connecting it to the initial state. |
void partial_evaluation | ( | const Element< S1, T1 > & | E, | |
const Element< S2, T2 > & | S, | |||
const typename Element< S2, T2 >::hstate_t & | p, | |||
M & | res | |||
) | [inline] |
This function computes a set of expression according to the rw_composition algorithm description.
E | lhs | |
S | rhs | |
p | the state from which the evaluation is run | |
res | the output map |
Definition at line 202 of file evaluation.hxx.
References Element::structure().
bool is_ambiguous | ( | const Element< A, AI > & | aut | ) | [inline] |
Test the ambiguity of automaton.
A
is ambiguous if there exists a word f
which is the label of two distinct accepting paths A
.aut | The automaton to test. |
Definition at line 58 of file is_ambiguous.hxx.
bool is_deterministic | ( | const Element< A, AI > & | a | ) | [inline] |
Test if an automaton is deterministic.
A realtime boolean automaton is deterministic if for each state s
and each letter l
, there is at most one outgoing transition labeled by s
, and if there is at most one initial state.
The empty automaton is deterministic (but not complete).
a | the automaton to check. |
Definition at line 95 of file is_deterministic.hxx.
Referenced by vcsn::co_minimization_moore(), vcsn::co_minimization_moore_here(), vcsn::complement_here(), vcsn::minimization_hopcroft(), vcsn::minimization_moore(), and vcsn::minimization_moore_here().
bool is_empty | ( | const Element< A, AI > & | a | ) | [inline] |
Return true if the automaton is empty (has no state), false otherwise.
Evaluate if an automaton is empty.
Return true if the automaton is empty (has no state), false otherwise.
a | The input automaton. |
Definition at line 30 of file is_empty.hxx.
bool is_letterized_transducer | ( | const Element< S, A > & | t | ) | [inline] |
Test the letter to letter features.
t | The transducer to test. |
Definition at line 50 of file is_letterized.hxx.
References Element::structure().
bool is_normalized_transducer | ( | const Element< S, A > & | t | ) | [inline] |
Test the normalization of transducer.
t | The transducer to test. |
Definition at line 50 of file is_normalized.hxx.
References Element::structure().
std::list< typename Series::monoid_t::alphabet_t::letter_t > flatten | ( | const Element< Series, T > & | exp | ) | [inline] |
This algorithm extracts the letters from a rational expression.
The flatten() function extracts the letters of a rational expression, keeping the order in which they appear in the expression. The result is just a std::list of letters, with letters having the same type as the expression's letter, i.e. Element<S, T>::monoid_elt_t::set_t::alphabet_t::letter_t.
exp | The expression to work on. |
Definition at line 123 of file krat_exp_flatten.hxx.
References KRatExpFlatten::flatten().
Element< A, AI > minimization_hopcroft | ( | const Element< A, AI > & | a | ) | [inline] |
Return the minimal automaton using the hopcroft algorithm.
Minimize a with Hopcroft algorithm.
a | The deterministic Boolean automaton to minimize. |
a must be deterministic.
a must be complete.
a | The automaton. |
a must be a complete automaton.
Definition at line 297 of file minimization_hopcroft.hxx.
References vcsn::is_complete(), vcsn::is_deterministic(), and Element::structure().
Element< A, AI > quotient | ( | const Element< A, AI > & | a | ) | [inline] |
Return the quotient of a non-deterministic acceptor.
This algorithms works with both Boolean and weighted automata.
a | The automaton to minimize. |
Definition at line 873 of file minimization_hopcroft.hxx.
References vcsn::is_realtime(), and SELECT.
Element< A, AI > minimization_moore | ( | const Element< A, AI > & | a | ) | [inline] |
Returns the minimal deterministic automaton associated to the input one.
Use Moore's algorithm to compute the minimal equivalent deterministic automaton. The complexity of this algorithm is O(n2). See minimize_hopcroft for O(nlogn).
ETA p123-125
a must be deterministic.
a must be complete.
Definition at line 245 of file minimization_moore.hxx.
References vcsn::is_complete(), vcsn::is_deterministic(), and Element::structure().
Element< A, AI > co_minimization_moore | ( | const Element< A, AI > & | a | ) | [inline] |
Returns the co-minimal co-deterministic automaton associated to the input one.
Use Moore's algorithm to compute the minimal equivalent co-deterministic automaton. The complexity of this algorithm is O(n2).
ETA p123-125
a must be co- deterministic.
a must be co- complete.
Definition at line 268 of file minimization_moore.hxx.
References vcsn::is_complete(), vcsn::is_deterministic(), Element::structure(), and vcsn::transpose().
void minimization_moore_here | ( | Element< A, AI > & | a | ) | [inline] |
Minimalize the deterministic input automaton.
Use Moore's algorithm to minimalize (in place) the input automaton. The complexity of this algorithm is O(n2). See minimize_hopcroft for O(nlogn).
ETA p123-125
a must be deterministic.
a must be complete.
Definition at line 233 of file minimization_moore.hxx.
References vcsn::is_complete(), vcsn::is_deterministic(), and Element::structure().
void co_minimization_moore_here | ( | Element< A, AI > & | a | ) | [inline] |
Co-minimalize the co-deterministic input automaton.
Use Moore's algorithm to co-minimalize (in place) the input automaton. The complexity of this algorithm is O(n2). See minimize_hopcroft for O(nlogn).
ETA p123-125
a must be co- deterministic.
a must be co- complete.
Definition at line 256 of file minimization_moore.hxx.
References vcsn::is_complete(), vcsn::is_deterministic(), Element::structure(), and vcsn::transpose().
Element< A, AI > normalize | ( | const Element< A, AI > & | a | ) | [inline] |
Return the fresh thompson-normalized automaton.
This function returns the thompson-normalized automaton corresponding to its input.
a | The automaton to normalize. |
Definition at line 63 of file normalized.hxx.
References Element::structure().
void normalize_here | ( | Element< A, AI > & | a | ) | [inline] |
In-place normalize to the thompson form.
This function performs the in-place thompson-normalization of its input.
a | An in/out parameter containing the automaton to normalize as input, and the normalized automaton as output. |
Definition at line 72 of file normalized.hxx.
References Element::structure().
bool is_normalized | ( | const Element< A, AI > & | a | ) | [inline] |
Return true if the input automaton is thompson-normalized.
This function indicates whether its input automaton is thompson-normalized or not.
a | The automaton to test. |
Definition at line 159 of file normalized.hxx.
References Element::structure().
void union_of_normalized_here | ( | Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
Do the in-place union of two thompson-normalized automata.
This function performs the in-place union of two thompson-normalized automata. The result is thompson-normalized.
lhs | An in/out parameter which is the left hand side of the union as input, and the operation result as output. | |
rhs | Right hand side of the union. |
Definition at line 113 of file normalized.hxx.
Element< A, AI1 > union_of_normalized | ( | const Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
Return the fresh union of two thompson-normalized automata.
This function returns a fresh automaton which is the union of input automata. It is thompson-normalized.
lhs | Left hand side of the union. | |
rhs | Right hand side of the union. |
Definition at line 121 of file normalized.hxx.
References Element::structure().
void concatenate_of_normalized_here | ( | Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
Do the in-place concatenation of two thompson-normalized automata.
This function performs the in-place concatenation of two thompson-normalized automata. The result is thompson-normalized.
lhs | An in/out parameter which is the left hand side of the concatenation as input, and the operation result as output. | |
rhs | Right hand side of the concatenation. |
Definition at line 240 of file normalized.hxx.
References Element::structure().
Element< A, AI1 > concatenate_of_normalized | ( | const Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
Return the fresh concatenation of two thompson-normalized automata.
This function returns a fresh automaton which is the concatenation of input automata. It is thompson-normalized.
lhs | Left hand side of the concatenation. | |
rhs | Right hand side of the concatenation. |
Definition at line 247 of file normalized.hxx.
References Element::structure().
void star_of_normalized_here | ( | Element< A, AI > & | a | ) | [inline] |
Do in-place star transformation on the thompson-normalized input.
This function performs the in-place star transformation of a thompson-normalized automaton. The result is thompson-normalized.
a | An in/out parameter which is the automaton to transform as input, and the operation result as output. |
Definition at line 283 of file normalized.hxx.
References Element::structure().
Element< A, AI > star_of_normalized | ( | const Element< A, AI > & | a | ) | [inline] |
Return the fresh star transformation of its normalized input.
This function performs a star transformation on its input, and returns it as a fresh automaton. The input must be thompson-normalized, and the result is thompson-normalized.
a | The automaton to run star transformation on. |
Definition at line 290 of file normalized.hxx.
References Element::structure().
void vcsn::compose | ( | const Element< S, T > & | lhs, | |
const Element< S, T > & | rhs, | |||
Element< S, T > & | ret | |||
) | [inline] |
Composition for weighted normalized and sub-normalized transducers, seen as automata over a free monoid product.
lhs | The left hand side transducer. | |
rhs | The right hand side transducer. | |
ret | The result transducer. |
Referenced by vcsn::do_compose(), and vcsn::do_u_compose().
Element<S, T> vcsn::compose | ( | const Element< S, T > & | lhs, | |
const Element< S, T > & | rhs | |||
) | [inline] |
Composition for weighted normalized and sub-normalized transducers, seen as automata over a free monoid product.
lhs | The left hand side transducer. | |
rhs | The right hand side transducer. |
void vcsn::u_compose | ( | const Element< S, T > & | lhs, | |
const Element< S, T > & | rhs, | |||
Element< S, T > & | ret | |||
) | [inline] |
Unambiguous composition for weighted normalized and sub-normalized transducers, seen as automata over a free monoid product.
lhs | The left hand side transducer. | |
rhs | The right hand side transducer. | |
ret | The result transducer. |
Element<S, T> vcsn::u_compose | ( | const Element< S, T > & | lhs, | |
const Element< S, T > & | rhs | |||
) | [inline] |
Unambiguous composition for weighted normalized and sub-normalized transducers, seen as automata over a free monoid product.
lhs | The left hand side transducer. | |
rhs | The right hand side transducer. |
void set_states | ( | const trans_t & | fmp_trans, | |
auto_t & | res, | |||
std::map< typename trans_t::hstate_t, typename auto_t::hstate_t > & | stmap | |||
) | [inline] |
Definition at line 28 of file projection.hxx.
void realtime_here | ( | Element< A, AI > & | a, | |
misc::direction_type | dir | |||
) | [inline] |
Modify an automaton in place to make it realtime.
An automaton over a free monoid is realtime if all its transitions are labeled by single letters of
. (Weights do not matter.)
This algorithm works in two steps: first transitions labeled by words are split into transitions labeled by singled letters separated by newly created states (if there is a weight associated to the word, it will be associated to the first letter and the other letter will be associated to the identity of the semiring); second the epsilon transitions are removed.
Removing epsilon transitions can be done in two ways: forward or backward. The dir argument can be used to control the direction and default to forward.
a | The automaton to make realtime. | |
dir | The direction of the epsilon removal algorithm. |
Definition at line 188 of file realtime.hxx.
References Element::structure().
Element< A, AI > realtime | ( | const Element< A, AI > & | a, | |
misc::direction_type | dir | |||
) | [inline] |
Create a realtime automaton from another one.
As realtime_here
, this algorithm builds a realtime automaton, but it returns a new one instead of changing the given one.
a | The automaton to make realtime. | |
dir | The direction of the epsilon removal algorithm. |
Definition at line 211 of file realtime.hxx.
References Element::structure().
Element<S, T> vcsn::realtime | ( | const Element< S, T > & | e | ) | [inline] |
Compute the realtime version of a rational expression or an automata.
This function is a wrapper which selects the realtime function either from realtime.hh or from krat_exp_realtime.hh.
When called upon an automaton, this function uses the functions declared in realtime.hh to make this automaton realtime using the forward epsilon removal.
When called with a rational expression, a function from krat_exp_realtime.hh is selected to expand words in the expression as a product of a letters.
void vcsn::realtime_here | ( | Element< S, T > & | e | ) | [inline] |
Modify a rational expression or automata in place to make it realtime.
This function is a wrapper thest selects the realtime() function from either realtime.hh or from krat_exp_realtime.hh.
It behaves exactly as realtime(), but do the operation in place.
bool vcsn::is_realtime | ( | const Element< S, T > & | e | ) | [inline] |
Test whether an automaton or a rational expression is realtime.
This function returns true if the input is realtime.
An automaton over a free monoid is realtime if all its transitions are labeled by single letters of
. (Weights do not matter.)
A rational expression is realtime if its litterals are only single letters of . E.g. "ab.ab*" is not rational while "a.b.(a.b)*" is.
e | The automaton or rational expression to test. |
Referenced by vcsn::complete_here(), vcsn::is_complete(), and vcsn::quotient().
vcsn::Element< SS, TT > & rw_to_fmp | ( | const Element< S, T > & | trans, | |
vcsn::Element< SS, TT > & | res | |||
) | [inline] |
Compute the equivalent FMP automaton of a Rational Weight transducer.
Please note that for the moment this function works only if the support of each transition is finite.
Definition at line 247 of file rw_to_fmp.hxx.
References Element::structure().
void search | ( | const Element< Automata< Series >, T > & | a, | |
const InputIterator & | begin, | |||
const InputIterator & | end, | |||
typename Element< Automata< Series >, T >::letter_t | eol, | |||
FoundFunctor & | f | |||
) | [inline] |
Search for a rational expression into a text.
This function searches a rational expression into a text, given a iterator on the text and an automaton which recognizes the corresponding langage. The result cannot spread over two lines.
a | The automaton which recognizes the searched words. | |
begin | An input iterator to the begining of the text. | |
end | An iterator to the end of the text. | |
eol | The character to use for ending a line. | |
f | A functor with an operator () method taking 3 InputIterator as argument which will be called each time a match is found. the first one points to the begining of the stream. The two following ones are respectively the first and the last position of the match in the stream. |
Definition at line 31 of file search.hxx.
static unsigned int vcsn::compute_distances | ( | const Element< Automata< Series >, T > & | a, | |
std::vector< StatesSet > & | distances | |||
) | [inline, static] |
Compute distances from initial states to final states.
For each i, compute the set of states reachable in i steps or less. the result is stored into a vector of set of states distances[i]. This algorithm stops when it first encounter a final state. The last i value is returned.
Definition at line 66 of file search.hxx.
References std::swap().
static std::pair<bool, unsigned int> vcsn::window_backsearch | ( | const misc::Window< InputIterator, typename Element< Automata< Series >, T >::letter_t > & | w, | |
const Element< Automata< Series >, T > & | a, | |||
const std::vector< StatesSet > & | distances | |||
) | [inline, static] |
Back search inside a window.
Returns whether the window is a potential match for the given automaton or not as the first element of the pair. The second element is the maximal value we can use to shift the window without skipping matches.
w | The window. | |
a | The automaton to use. | |
distances | Distances get from compute_distances(). |
Definition at line 124 of file search.hxx.
References std::swap().
void standardize | ( | Element< A, AI > & | a | ) | [inline] |
Returns a standard automaton associated to the input.
a | The automaton to standardize |
Definition at line 84 of file standard.hxx.
References Element::structure().
bool is_standard | ( | const Element< A, AI > & | a | ) | [inline] |
Returns true if the input automaton is standard.
a | The automaton to test |
Definition at line 179 of file standard.hxx.
References Element::structure().
void union_of_standard_here | ( | Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
In-place union of two standard automata.
This function make the union of two standard automata. The result is a standard automaton.
lhs | The first automaton (will contain the result) | |
rhs | The second automaton |
Definition at line 138 of file standard.hxx.
References Element::structure().
Referenced by vcsn::union_of_standard().
Element< A, AI1 > union_of_standard | ( | const Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
Return a fresh union of two standard automata.
As union_of_standard_here
, this function build the union of two automatons, but it builds a new one.
lhs | The first automaton | |
rhs | The second automaton |
Definition at line 145 of file standard.hxx.
References vcsn::union_of_standard_here().
void concat_of_standard_here | ( | Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
In-place concatenation of two standard automata.
This function make the concatenation of two standard automata. The result is a standard automaton.
lhs | The first automaton (will contain the result) | |
rhs | The second automaton |
Definition at line 267 of file standard.hxx.
Element< A, AI1 > concat_of_standard | ( | const Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
Return a fresh concatenation of two standard automata.
As concat_of_standard_here
, this function build the union of two automatons, but it builds a new one.
lhs | The first automaton | |
rhs | The second automaton |
Definition at line 274 of file standard.hxx.
References Element::structure().
void star_of_standard_here | ( | Element< A, AI > & | a | ) | [inline] |
In-place star transformation of a standard automata.
This function make the star transformation of a standard automaton, and replace those given by the result.
a | The automaton to transform |
Definition at line 317 of file standard.hxx.
Element< A, AI > star_of_standard | ( | const Element< A, AI > & | a | ) | [inline] |
Return the fresh star transformation of a standard automata.
As star_of_standard_here
, this function applies star on an automaton, but it build a new automaton.
a | The automaton on which star must be applied. |
Definition at line 324 of file standard.hxx.
References Element::structure().
void standard_of | ( | Element< A, T > & | a, | |
const Exp & | e | |||
) | [inline] |
Convert a rational expression into a standard automaton.
e | The expression to convert. | |
a | The automaton to store the result. |
Definition at line 228 of file standard_of.hxx.
References Element::structure().
Element< A, AI > sub_automaton | ( | const Element< A, AI > & | a, | |
const HStatesSet & | s, | |||
bool | check_states = true | |||
) | [inline] |
Returns a fresh automaton that is the sub-automaton defined by a set.
a | The automaton into which we have to extract the sub-automaton. | |
s | The set of states of the sub-automaton included in the state of 'a'. | |
check_states | A flag to enable/disable the inclusion checking. |
Definition at line 59 of file sub_automaton.hxx.
References Element::structure().
Referenced by vcsn::accessible(), vcsn::coaccessible(), and vcsn::trim().
void sub_automaton_here | ( | Element< A, AI > & | a, | |
const HStatesSet & | s, | |||
bool | check_states = true | |||
) | [inline] |
Select a sub-automaton into a given automaton.
a | The automaton into which we have to extract the sub-automaton. | |
s | The set of states of the sub-automaton included in the state of 'a'. | |
check_states | A flag to enable/disable the inclusion checking. |
Definition at line 72 of file sub_automaton.hxx.
References Element::structure().
Referenced by vcsn::accessible_here(), vcsn::coaccessible_here(), vcsn::do_u_compose(), and vcsn::trim_here().
Element<S, T> vcsn::sub_normalize | ( | const Element< S, T > & | a | ) | [inline] |
Sub-normalize a FMP transducer.
void vcsn::sub_normalize | ( | const Element< S, T1 > & | a, | |
Element< S, T2 > & | res | |||
) | [inline] |
Sub-normalize a FMP transducer.
void vcsn::sub_normalize_here | ( | Element< S, T > & | a | ) | [inline] |
Sub-normalize a FMP transducer, in place version.
a | Input automaton. |
bool vcsn::is_sub_normalized | ( | const Element< S, T > & | a | ) | [inline] |
Check if a FMP transducer is sub-normalized.
void sum_here | ( | Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
In place summing of two automata.
This function adds states and transitions of an automaton to states and transitions of a second automaton.
lhs | Destination of the summing | |
rhs | Source of summing |
Definition at line 88 of file sum.hxx.
References Element::structure().
Element< A, AI1 > sum | ( | const Element< A, AI1 > & | lhs, | |
const Element< A, AI2 > & | rhs | |||
) | [inline] |
Summing of two automata.
This function returns the fresh union of two automata. It put transitions and states of the two automata together, and create a news one with the result.
lhs | First automaton to sum | |
rhs | Second automaton to sum |
Definition at line 95 of file sum.hxx.
References Element::structure().
void thompson_of | ( | Element< A, T > & | out, | |
const rat::exp< Letter, Weight > & | kexp | |||
) | [inline] |
The Thompson automaton associated to the krat expression.
This function build the automaton associated to the rational expression implemented by a krat_exp, using Thompson algorithm.
out | The resulting automaton | |
kexp | The rational expression |
Definition at line 209 of file thompson.hxx.
References Element::structure().
Element<Automata<S>, AutoType> vcsn::thompson_of | ( | const Element< S, T > & | exp | ) | [inline] |
The Thompson automaton associated to the krat expression.
This function build the automaton associated to the rational expression implemented by a krat_exp, using Thompson algorithm. The kind of returned automaton is a default one.
exp | The rational expression |
void transpose | ( | Element< A, AI1 > & | dst, | |
const Element< A, AI2 > & | from | |||
) | [inline] |
Transposition of an automaton.
This function copy in dst
the transposition of the automaton from
.
dst | Destination | |
from | Automaton to transpose |
Definition at line 29 of file algorithms/transpose.hxx.
References vcsn::transpose_view().
Element< A, AI > transpose | ( | const Element< A, AI > & | from | ) | [inline] |
Return a fresh transposed automaton.
This function returns the transposition of an automaton.
from | Automaton to transpose. |
Definition at line 43 of file algorithms/transpose.hxx.
References Element::structure(), and vcsn::transpose().
std::set< typename Element< A, AI >::hstate_t > useful_states | ( | const Element< A, AI > & | a | ) | [inline] |
Returns a useful states of the automaton.
This functions returns the states that are reachable and co-reachable.
a | The input automaton. |
Definition at line 56 of file trim.hxx.
References Element::structure().
Referenced by vcsn::do_u_compose(), vcsn::trim(), and vcsn::trim_here().
Element< A, AI > trim | ( | const Element< A, AI > & | a | ) | [inline] |
Return a fresh automaton in which non useful states are removed.
a | The input automaton. |
Definition at line 63 of file trim.hxx.
References vcsn::sub_automaton(), and vcsn::useful_states().
Referenced by vcsn::has_succ_comp().
void trim_here | ( | Element< A, AI > & | a | ) | [inline] |
Trim a.
Remove non useful states from the automaton.
a | The input automaton. |
Definition at line 70 of file trim.hxx.
References vcsn::sub_automaton_here(), and vcsn::useful_states().