Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

Algorithms


Files

file  accessible.hh
 Algorithms for accessible/coaccessible states computation.

file  aci_canonical.hh
 This file contains the declaration for the canonical() algorithm.

file  aut_to_exp.hh
 This file provides converter from automaton to expression.

file  backward_closure.hh
 This files declares the backward closure algorithm.

file  backward_realtime.hh
 Algorithms to make an automaton realtime.

file  complement.hh
 Complementation algorithm for Boolean automata.

file  complete.hh
 Completion algorithm for deterministic and Boolean automaton.

file  concatenate.hh
 This file provides the general concatenation algorithm.

file  derivatives_automaton.hh
 Provides a converter from expression to automaton based on derivatives.

file  determinize.hh
 This file provides the determinization algorithm for Boolean automata.

file  eval.hh
 This file provides the evaluation of a word w.r.t an automaton.

file  evaluation.hh
 Undocumented stuff.

file  extension.hh
 This file contains declarations for extension().

file  finite_support_conversion.hh
 Conversion between finite support application types.

file  forward_closure.hh
 Forward closure algorithm.

file  forward_realtime.hh
 Algorithms to make an automaton realtime.

file  is_letterized.hh
 This file contains letter-to-letter feature testing.

file  is_normalized.hh
 This file contains a test for transducer normalization.

file  is_realtime.hh
 This file contains a test for realtime transducers.

file  isomorph.hh
 This files contains the declaration for the is_isomorph() algorithm.

file  krat_exp_cderivation.hh
 This file contains the declaration for the cderivate() algorithms.

file  krat_exp_constant_term.hh
 This file contains the declaration for the constant_term() algorithm.

file  krat_exp_derivation.hh
 This file contains the declaration for the derivate() algorithms.

file  krat_exp_flatten.hh
 This file holds the declaration of the flatten() algorithm.

file  krat_exp_linearize.hh
 This file contains the declarations for the linearize() algorithm.

file  krat_exp_partial_derivation.hh
 This file contains the declarations for the partial_derivate() algorithm.

file  krat_exp_print.hh
 This file contains the declarations for the krat_exp_print() 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  product.hh
 This file contains the declarations of product().

file  projection.hh
 Undocumented stuff.

file  realtime.hh
 General algorithms concerning realtime aspect of automata.

file  realtime_composition.hh
 Undocumented stuff.

file  realtime_decl.hh
 Declaration of the realtime() function.

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  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
 This file contains the declaration of useful_states() and trim().


Classes

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 T> Element< A, T > vcsn::determinize (const Element< A, T > &a)
 Returns the determinized of a Boolean automaton.

template<typename A, typename T> Element< A, T > vcsn::determinize (const Element< A, T > &a, std::map< hstate_t, std::set< hstate_t > > &)
 Returns the determinized of a Boolean automaton.


Evalutation algorithm's internals

template<typename SE, typename TE, typename ST, typename TT, typename M> void vcsn::partial_evaluation (const Element< SE, TE > &exp, const Element< ST, TT > &trans, M &state_exp_pair)
 The following functions are absolutely not for public calls.

template<typename SA, typename TA, typename M> void vcsn::partial_elimination (const Element< SA, TA > &a, M &state_exp_pair)
 The following functions are absolutely not for public calls.

template<typename SA, typename TA, typename ST, typename TT, typename M> void vcsn::partial_1 (const Element< SA, TA > &, const Element< ST, TT > &, M &)
 The following functions are absolutely not for public calls.

template<typename SA, typename TA, typename ST, typename TT, typename Exp> void vcsn::partial_2 (const Element< SA, TA > &, const Element< ST, TT > &, const hstate_t, Exp &)
 The following functions are absolutely not for public calls.

template<typename SA, typename TA, typename ST, typename TT, typename M> void vcsn::partial_3 (const Element< SA, TA > &, const Element< ST, TT > &, const hstate_t, M &)
 The following functions are absolutely not for public calls.


Product algorithm

template<typename A, typename T, typename U> Element< A, T > vcsn::product (const Element< A, T > &lhs, const Element< A, U > &rhs)
 Returns a fresh automaton that is the product of the two input ones.

template<typename A, typename T, typename U> Element< A, T > vcsn::product (const Element< A, T > &lhs, const Element< A, U > &rhs, std::map< hstate_t, std::pair< hstate_t, hstate_t > > &)
 Returns a fresh automaton that is the product of the two input ones.


Enumerations

enum  vcsn::realtime_type
 Enum to indicate which kind of realtime algorithms must be used.


Functions

template<typename A, typename T> std::set< hstate_t > vcsn::accessible_states (const Element< A, T > &a)
 Return accessible states.

template<typename A, typename T> Element< A, T > vcsn::accessible (const Element< A, T > &a)
 Extract the sub-automaton composed of accessible states.

template<typename A, typename T> void vcsn::accessible_here (Element< A, T > &a)
 In-place extract the sub-automaton of accessible states.

template<typename A, typename T> std::set< hstate_t > vcsn::coaccessible_states (const Element< A, T > &a)
 Return co-accessible states.

template<typename A, typename T> Element< A, T > vcsn::coaccessible (const Element< A, T > &a)
 Extract the sub-automaton composed of co-accessible states.

template<typename A, typename T> void vcsn::coaccessible_here (Element< A, T > &a)
 In-place extract the sub-automaton of co-accessible states.

template<class Series, class T> Element< Series, T > vcsn::canonical (const Element< Series, T > &exp)
 Transform a krat expression into its canonical form, following aci-rules.

template<typename A, typename T> Element< A, T >::series_elt_t vcsn::aut_to_exp (const Element< A, T > &a)
 Returns a series which describes the language of the automaton.

template<typename A, typename T, typename Chooser_> Element< A, T >::series_elt_t vcsn::aut_to_exp (const Element< A, T > &a, const Chooser_ &c)
 Returns a series which describes the language of the automaton.

template<typename A, typename T> void vcsn::backward_closure_here (Element< A, T > &a)
 In place backward closure of an automaton.

template<typename A, typename T> Element< A, T > vcsn::backward_closure (const Element< A, T > &a)
 Backward closure of an automaton.

template<typename A, typename T> void vcsn::backward_realtime_here (Element< A, T > &a)
 In place modification of the automaton to make it realtime.

template<typename A, typename T> Element< A, T > vcsn::backward_realtime (const Element< A, T > &a)
 Returns a fresh realtime automaton.

template<typename A, typename T, typename Exp> void vcsn::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 vcsn::brzozowski (Element< A, T > &, const Exp &)
 Build an automaton from an expression using the Brzozowski construction.

template<typename A, typename T> void vcsn::complement_here (Element< A, T > &a)
 Complement in place the set of final states.

template<typename A, typename T> Element< A, T > vcsn::complement (const Element< A, T > &a)
 Complement the set of final states.

template<typename A, typename T> void vcsn::complete_here (Element< A, T > &a)
 Make the transition function of an automaton total w.r.t alphabet.

template<typename A, typename T> Element< A, T > vcsn::complete (const Element< A, T > &a)
 Make the transition function of an automaton total w.r.t alphabet.

template<class A, class T> bool vcsn::is_complete (const Element< A, T > &a)
 Test if the transition function is complete for each state.

template<class A, class T> Element< A, T > vcsn::concatenate (const Element< A, T > &lhs, const Element< A, T > &rhs)
 Return the concatenation of two automata.

template<class A, class T> void vcsn::concatenate_here (Element< A, T > &lhs, const Element< A, T > &rhs)
 In place concatenation of two automata.

template<typename A, typename T, typename Exp> void vcsn::derivatives_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 > vcsn::derivatives_automaton (const Exp &e)
 Convert a krat expression into an automaton using derivatives.

template<typename A, typename T> bool vcsn::is_deterministic (const Element< A, T > &a)
 Test if an automaton is deterministic.

template<typename A, typename T, typename W> Element< A, T >::semiring_elt_t vcsn::eval (const Element< A, T > &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 vcsn::evaluation (const Element< SA, TA > &, const Element< ST, TT > &, Element< SARET, TARET > &)
 Evaluate for a "letterized" automaton and a realtime transducer.

template<typename S, typename T> identity_transducer_helper<
S, T >::ret 		vcsn::extension (const Element< S, T > &)
 Extend an automaton to a transducer.

template<typename SA, typename TA, typename ST, typename TT> Element< ST, TT > vcsn::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 vcsn::finite_support_convert (Element< S, T > &dst, const Element< Ss, Ts > &org)
 Finite support conversion.

template<typename A, typename T> void vcsn::forward_closure_here (Element< A, T > &a)
 In-place forward closure algorithm.

template<typename A, typename T> Element< A, T > vcsn::forward_closure (const Element< A, T > &a)
 Forward closure algorithm.

template<typename A, typename T> void vcsn::forward_realtime_here (Element< A, T > &a)
 In place modification of the automaton to make it realtime.

template<typename A, typename T> Element< A, T > vcsn::forward_realtime (const Element< A, T > &a)
 Returns a fresh realtime automaton.

template<typename S, typename A> bool vcsn::is_letterized_transducer (const Element< S, A > &t)
 Test the letter to letter features.

template<typename S, typename A> bool vcsn::is_normalized_transducer (const Element< S, A > &t)
 Test the normalization of transducer.

template<typename A, typename T> bool vcsn::is_isomorph (const Element< A, T > &a, const Element< A, T > &b)
 Returns true if the two automata are isomorph.

template<class Series, class T, class Letter> Element< Series, T > vcsn::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 > vcsn::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 > 		vcsn::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 > 		vcsn::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 > 		vcsn::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 > vcsn::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 		vcsn::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 > 		vcsn::partial_derivate (const Element< Series, T > &exp, Letter a)
 The partial derivative of the krat expression w.r.t to a letter.

template<typename Letter, typename Weight> void vcsn::krat_exp_print (const rat::exp< Letter, Weight > &kexp, const unsigned &mode=0)
 Print a krat expression under several formats.

template<class S, class T> Element< S, T > vcsn::letter_to_letter_composition (const Element< S, T > &lhs, const Element< S, T > &rhs)
 Undocumented.

template<typename A, typename T> Element< A, T > vcsn::minimization_hopcroft (const Element< A, T > &a)
 Return the minimal automaton using the hopcroft algorithm.

template<typename A, typename T> Element< A, T > vcsn::quotient (const Element< A, T > &a)
 Return the quotient of a non deterministic acceptor.

template<typename A, typename T> Element< A, T > vcsn::minimization_moore (const Element< A, T > &a)
 Returns the minimal deterministic automaton associated to the input one.

template<typename A, typename T> void vcsn::minimization_moore_here (Element< A, T > &a)
 Minimalize the deterministic input automaton.

template<typename A, typename T> Element< A, T > vcsn::normalize (const Element< A, T > &a)
 Return the fresh thompson-normalized automaton.

template<typename A, typename T> void vcsn::normalize_here (Element< A, T > &a)
 In-place normalize to the thompson form.

template<typename A, typename T> bool vcsn::is_normalized (const Element< A, T > &a)
 Return true if the input automaton is thompson-normalized.

template<typename A, typename T, typename U> void vcsn::union_of_normalized_here (Element< A, T > &lhs, const Element< A, U > &rhs)
 Do the in-place union of two thompson-normalized automata.

template<typename A, typename T, typename U> Element< A, T > vcsn::union_of_normalized (const Element< A, T > &lhs, const Element< A, U > &rhs)
 Return the fresh union of two thompson-normalized automata.

template<typename A, typename T, typename U> void vcsn::concatenate_of_normalized_here (Element< A, T > &lhs, const Element< A, U > &rhs)
 Do the in-place concatenation of two thompson-normalized automata.

template<typename A, typename T, typename U> Element< A, T > vcsn::concatenate_of_normalized (const Element< A, T > &lhs, const Element< A, U > &rhs)
 Return the fresh concatenation of two thompson-normalized automata.

template<typename A, typename T> void vcsn::star_of_normalized_here (Element< A, T > &a)
 Do in-place star transformation on the thompson-normalized input.

template<typename A, typename T> Element< A, T > vcsn::star_of_normalized (const Element< A, T > &a)
 Return the fresh star transformation of its normalized input.

template<typename A, typename T> void vcsn::realtime_here (Element< A, T > &a, realtime_type type)
 In place modification of the automaton to make it realtime.

template<typename A, typename T> Element< A, T > vcsn::realtime (const Element< A, T > &a, realtime_type type)
 Returns a fresh realtime automaton.

template<typename S, typename T> void vcsn::realtime_composition (const Element< S, T > &, const Element< S, T > &, Element< S, T > &)
 Composition for realtime transducers.

template<typename S, typename T> Element< S, T > vcsn::realtime (const Element< S, T > &e)
 Calls the do_realtime function for rational expression or automata.

template<typename S, typename T> void vcsn::realtime_here (Element< S, T > &e)
 Calls the do_realtime_here function for rational expression or automata.

template<typename S, typename T> bool vcsn::is_realtime (const Element< S, T > &e)
 Test whether an automaton or a regular expression is realtime.

template<class InputIterator, class FoundFunctor, class Series, class T> void vcsn::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> unsigned int vcsn::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> std::pair< bool, unsigned
int > 		vcsn::window_backsearch (const utility::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> InputIterator vcsn::confirm_and_report_match (const utility::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 T> void vcsn::standardize (Element< A, T > &a)
 Returns a standard automaton associated to the input.

template<typename A, typename T> bool vcsn::is_standard (const Element< A, T > &a)
 Returns true if the input automaton is standard.

template<typename A, typename T, typename U> void vcsn::union_of_standard_here (Element< A, T > &lhs, const Element< A, U > &rhs)
 In-place union of two standard automata.

template<typename A, typename T, typename U> Element< A, T > vcsn::union_of_standard (const Element< A, T > &lhs, const Element< A, U > &rhs)
 Return a fresh union of two standard automata.

template<typename A, typename T, typename U> void vcsn::concat_of_standard_here (Element< A, T > &lhs, const Element< A, U > &rhs)
 In-place concatenation of two standard automata.

template<typename A, typename T, typename U> Element< A, T > vcsn::concat_of_standard (const Element< A, T > &lhs, const Element< A, U > &rhs)
 Return a fresh concatenation of two standard automata.

template<typename A, typename T> void vcsn::star_of_standard_here (Element< A, T > &a)
 In-place star transformation of a standard automata.

template<typename A, typename T> Element< A, T > vcsn::star_of_standard (const Element< A, T > &a)
 Return the fresh star transformation of a standard automata.

template<typename A, typename T, typename Exp> void vcsn::standard_of (Element< A, T > &a, const Exp &e)
 Convert a rational expression into a standard automaton.

template<typename A, typename T, typename Exp> Element< A, T > vcsn::standard_of (const Exp &e)
 Convert a rational expression into a standard automaton.

template<typename A, typename T, typename StatesSet> Element< A, T > vcsn::sub_automaton (const Element< A, T > &a, const StatesSet &s, bool check_states=true)
 Returns a fresh automaton that is the sub-automaton defined by a set.

template<typename A, typename T, typename StatesSet> void vcsn::sub_automaton_here (Element< A, T > &a, const StatesSet &s, bool check_states=true)
 Select a sub-automaton into a given automaton.

template<typename A, typename T, typename U> void vcsn::sum_here (Element< A, T > &lhs, const Element< A, U > &rhs)
 In place summing of two automata.

template<typename A, typename T, typename U> Element< A, T > vcsn::sum (const Element< A, T > &lhs, const Element< A, U > &rhs)
 Summing of two automata.

template<typename A, typename T, typename Letter, typename Weight> void vcsn::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 > vcsn::thompson_of (const Element< S, T > &exp)
 The Thompson automaton associated to the krat expression.

template<typename lhs_t, typename rhs_t> void vcsn::transpose (lhs_t &dst, const rhs_t &from)
 Transposition of an automaton.

template<typename auto_t> auto_t vcsn::transpose (const auto_t &from)
 Return a fresh transposed automaton.

template<typename A, typename T> std::set< hstate_t > vcsn::useful_states (const Element< A, T > &a)
 Returns a useful states of the automaton (start reachable and final co-).

template<typename A, typename T> Element< A, T > vcsn::trim (const Element< A, T > &a)
 Return a fresh automaton in which non useful states are removed.

Function Documentation

std::set< hstate_t > accessible_states (  const Element< A, T > &  a  ) 
 

Return accessible states.

This functions returns the accessible states set of its input automaton.

Parameters:
a The input automaton.
See also:
accessible(), coaccessible(), coaccessible_states()

Element< A, T > accessible (  const Element< A, T > &  a  ) 
 

Extract the sub-automaton composed of accessible states.

This function returns a fresh sub-automaton of its input containing only accessible states.

Parameters:
a The input automaton.
See also:
accessible_here(), accessible_states(), coaccessible(), coaccessible_states()

void accessible_here (  Element< A, T > &  a  ) 
 

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.

Parameters:
a An in/out parameter which contains the automaton to work on as input and the result as output.
See also:
accessible(), accessible_states(), coaccessible(), coaccessible_states()

std::set< hstate_t > coaccessible_states (  const Element< A, T > &  a  ) 
 

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.

Parameters:
a The input automaton.
See also:
coaccessible(), accessible(), accessible_states()

Element< A, T > coaccessible (  const Element< A, T > &  a  ) 
 

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.

Parameters:
a The input automaton.
See also:
coaccessible_here(), coaccessible_states(), accessible(), accessible_states()

void coaccessible_here (  Element< A, T > &  a  ) 
 

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.

Parameters:
a An in/out parameter which contains the automaton to work on as input and the result as output.
See also:
coaccessible(), coaccessible_states(), accessible(), accessible_states()

Element< A, T >::series_elt_t aut_to_exp (  const Element< A, T > &  a  ) 
 

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.

Parameters:
a The automaton to convert.
Returns:
A rational series that describes the language of the automaton.
See also:
generalized()

Element< A, T >::series_elt_t aut_to_exp (  const Element< A, T > &  a,
const Chooser_ &  c
) 
 

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.

Parameters:
a The automaton to work on.
c An object-function that returns the next state to remove from the current state and the automaton.
Returns:
A rational series that describes the language of the automaton.
See also:
generalized()

void backward_closure_here (  Element< A, T > &  a  ) 
 

In place backward closure 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.

Parameters:
a The weighted automaton to close.
See also:
forward_closure_here(), forward_closure(), backward_closure_here()
Author:
Thanh-Hoc NGUYEN

Element< A, T > backward_closure (  const Element< A, T > &  a  ) 
 

Backward closure of an automaton.

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.

Parameters:
a The weighted automaton to close.
See also:
forward_closure(), forward_closure_here(), backward_closure_here()
Author:
Thanh-Hoc NGUYEN

void backward_realtime_here (  Element< A, T > &  a  ) 
 

In place modification of the automaton to make it realtime.

This function make an automaton realtime, using backward version of closure for building.

Parameters:
a The automaton to make realtime.
See also:
realtime(), backward_realtime(), forward_realtime_here()

Element< A, T > backward_realtime (  const Element< A, T > &  a  ) 
 

Returns a fresh realtime automaton.

This fonction build a fresh realtime automaton from those given, using backward version of closure.

Parameters:
a The automaton to make realtime.
See also:
realtime(), backward_realtime_here(), forward_realtime()

void complement_here (  Element< A, T > &  a  ) 
 

Complement in place the set of final states.

Parameters:
a The deterministic Boolean automaton to complement.
Note:
The input automaton must be complete and deterministic.
See also:
complement()
Author:
Yann Régis-Gianas

Element< A, T > complement (  const Element< A, T > &  a  ) 
 

Complement the set of final states.

Parameters:
a the deterministic Boolean automaton to complement.
Note:
the input automaton must be complete and deterministic.
See also:
complement_here()
Author:
Yann Régis-Gianas

void complete_here (  Element< A, T > &  a  ) 
 

Make the transition function of an automaton total w.r.t alphabet.

Note:
This algorithm works in place.
Parameters:
a the deterministic and Boolean automaton to complete.
See also:
complete(), is_complete()
Author:
Yann Régis-Gianas

Element< A, T > complete (  const Element< A, T > &  a  ) 
 

Make the transition function of an automaton total w.r.t alphabet.

Note:
This algorithm returns a fresh automaton.
Parameters:
a the deterministic and Boolean automaton to complete.
See also:
complete_here(), is_complete()
Author:
Yann Régis-Gianas

bool is_complete (  const Element< A, T > &  a  ) 
 

Test if the transition function is complete for each state.

Parameters:
a The Boolean automaton to test.
Returns:
true if the transition function of e is complete w.r.t alphabet.
See also:
complete(), complete_here()
Author:
Yann Régis-Gianas

Element< A, T > concatenate (  const Element< A, T > &  lhs,
const Element< A, T > &  rhs
) 
 

Return the concatenation of two automata.

This function produces a new automata that realizes L(lhs).L(rhs).

Parameters:
lhs The first automaton.
rhs The second automaton.
See also:
concatenate_here()
Returns:
A fresh automaton that is the concatenation of lhs and rhs.

void concatenate_here (  Element< A, T > &  lhs,
const Element< A, T > &  rhs
) 
 

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.

Parameters:
lhs The first automaton.
rhs The second automaton.
See also:
concatenate()
Author:
Yann Regis-Gianas.

void derivatives_automaton (  Element< A, T > &  a,
const Exp &  e
) 
 

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.

Parameters:
a An automaton to store the results.
e The expression to convert.
Note:
'a' is generally an empty automaton. It enables the choice of the series to work with. Thus, the series can be different from the expresion ones.

Element< A, T > derivatives_automaton (  const Exp &  e  ) 
 

Convert a krat expression into an automaton using derivatives.

Parameters:
e The expression to convert.
Returns:
A fresh automaton which recognizes the language denoted by 'e'.
Note:
The series of the expression are used to define the automaton.

Element< A, T > determinize (  const Element< A, T > &  a  ) 
 

Returns the determinized of a Boolean automaton.

Parameters:
a The Boolean automaton to determinize.
Returns:
A fresh Boolean automaton that is the determinization of 'a'.

Element< A, T > determinize (  const Element< A, T > &  a,
std::map< hstate_t, std::set< hstate_t > > & 
) 
 

Returns the determinized of a Boolean automaton.

Parameters:
a The Boolean automaton to determinize.
Returns:
A fresh Boolean automaton that is the determinization of 'a'.

bool is_deterministic (  const Element< A, T > &  a  ) 
 

Test if an automaton is deterministic.

Parameters:
a A Boolean automaton.
Returns:
true if 'a' is deterministic.

Element< A, T >::semiring_elt_t eval (  const Element< A, T > &  a,
const W &  word
) 
 

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.

identity_transducer_helper< S, T >::ret extension (  const Element< S, T > &   ) 
 

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 > &  ,
const Element< ST, TT > & 
) 
 

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.

void finite_support_convert (  Element< S, T > &  dst,
const Element< Ss, Ts > &  org
) 
 

Finite support conversion.

This algorithm copies the value of a finite support application to another, possibly changing its type.

Parameters:
org The source application to convert.
dst The destination application.

void forward_closure_here (  Element< A, T > &  a  ) 
 

In-place forward closure algorithm.

Complete the given automaton into a copy to make it close over epsilon transition.

Parameters:
a The weighted automaton to close.
See also:
forward_closure(), backward_closure(), backward_closure_here()

Element< A, T > forward_closure (  const Element< A, T > &  a  ) 
 

Forward closure algorithm.

Complete the given automaton into a copy to make it close over epsilon transition.

Parameters:
a The weighted automaton to close.
See also:
forward_closure(), backward_closure(), backward_closure_here()

void forward_realtime_here (  Element< A, T > &  a  ) 
 

In place modification of the automaton to make it realtime.

This function make an automaton realtime, using forward version of closure for building.

Parameters:
a The automaton to make realtime.
See also:
realtime(), forward_realtime(), backward_realtime_here()

Element< A, T > forward_realtime (  const Element< A, T > &  a  ) 
 

Returns a fresh realtime automaton.

This fonction build a fresh realtime automaton from those given, using forward version of closure.

Parameters:
a The automaton to make realtime.
See also:
realtime(), forward_realtime_here(), backward_realtime()

bool is_letterized_transducer (  const Element< S, A > &  t  ) 
 

Test the letter to letter features.

Parameters:
t The transducer to test.
Returns:
true if the transducer is letter to letter.

bool is_normalized_transducer (  const Element< S, A > &  t  ) 
 

Test the normalization of transducer.

Parameters:
t The transducer to test.
Returns:
true if the transducer is normalized.

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.

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.

Parameters:
exp The expression to work on.
Author:
Thomas Claveirole <thomas.claveirole@lrde.epita.fr>

Element< A, T > minimization_hopcroft (  const Element< A, T > &  a  ) 
 

Return the minimal automaton using the hopcroft algorithm.

Parameters:
a The deterministic Boolean automaton to minimize.
Returns:
A fresh automaton that is the canonical minimal automaton of 'a'.

Element< A, T > quotient (  const Element< A, T > &  a  ) 
 

Return the quotient of a non deterministic acceptor.

Parameters:
a The Boolean automaton to minimize.
Returns:
A fresh automaton that is the quotient of 'a'.

Element< A, T > minimization_moore (  const Element< A, T > &  a  ) 
 

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

See also:
http://cs.engr.uky.edu/~lewis/essays/compilers/min-fa.html
Author:
Louis-Noel Pouchet <louis-noel.pouchet@lrde.epita.fr>
Bug:
Put the precondition.

void minimization_moore_here (  Element< A, T > &  a  ) 
 

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

See also:
http://cs.engr.uky.edu/~lewis/essays/compilers/min-fa.html
Author:
Louis-Noel Pouchet <louis-noel.pouchet@lrde.epita.fr>

Element< A, T > normalize (  const Element< A, T > &  a  ) 
 

Return the fresh thompson-normalized automaton.

This function returns the thompson-normalized automaton corresponding to its input.

Parameters:
a The automaton to normalize.
See also:
normalize_here(), is_normalized(), union_of_normalized(), concatenate_of_normalized(), star_of_normalized().

void normalize_here (  Element< A, T > &  a  ) 
 

In-place normalize to the thompson form.

This function performs the in-place thompson-normalization of its input.

Parameters:
a An in/out parameter containing the automaton to normalize as input, and the normalized automaton as output.
See also:
normalize, is_normalized(), union_of_normalized(), concatenate_of_normalized(), star_of_normalized().

bool is_normalized (  const Element< A, T > &  a  ) 
 

Return true if the input automaton is thompson-normalized.

This function indicates whether its input automaton is thompson-normalized or not.

Parameters:
a The automaton to test.
See also:
normalize(), union_of_normalized(), concatenate_of_normalized(), star_of_normalized().

void union_of_normalized_here (  Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

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.

Parameters:
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.
See also:
union_of_normalized(), concatenate_of_normalized(), star_of_normalized(), normalize(), is_normalized().

Element< A, T > union_of_normalized (  const Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

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.

Parameters:
lhs Left hand side of the union.
rhs Right hand side of the union.
See also:
union_of_normalized_here(), concatenate_of_normalized(), star_of_normalized(), normalize(), is_normalized().

void concatenate_of_normalized_here (  Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

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.

Parameters:
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.
See also:
concatenate_of_normalized(), union_of_normalized(), star_of_normalized(), normalize(), is_normalized().

Element< A, T > concatenate_of_normalized (  const Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

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.

Parameters:
lhs Left hand side of the concatenation.
rhs Right hand side of the concatenation.
See also:
concatenate_of_normalized_here(), union_of_normalized(), star_of_normalized(), normalize, is_normalized().

void star_of_normalized_here (  Element< A, T > &  a  ) 
 

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.

Parameters:
a An in/out parameter which is the automaton to transform as input, and the operation result as output.
See also:
star_of_normalized(), concatenate_of_normalized(), union_of_normalized(), normalize(), is_normalized().

Element< A, T > star_of_normalized (  const Element< A, T > &  a  ) 
 

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.

Parameters:
a The automaton to run star transformation on.
See also:
star_of_normalized_here(), concatenate_of_normalized(), union_of_normalized(), normalize(), is_normalized().

void realtime_here (  Element< A, T > &  a,
realtime_type  type
) 
 

In place modification of the automaton to make it realtime.

This algorithm makes an automaton realtime. It calls forward_realtime or backward_realtime according to type given. The type may not be precised, it is the forward_realtime which is used by default.

Parameters:
a The automaton to make realtime.
type The type of algorithm used.
See also:
realtime(), forward_realtime_here(), backward_realtime_here()

Element< A, T > realtime (  const Element< A, T > &  a,
realtime_type  type
) 
 

Returns a fresh realtime automaton.

As realtime_here, it build a realtime automaton, but it returns a new one instead of changing the given one.

Parameters:
a The automaton to make realtime.
type The type of algorithm used.
See also:
realtime_here(), forward_realtime(), backward_realtime()

Element< S, T > realtime (  const Element< S, T > &  e  ) 
 

Calls the do_realtime function for rational expression or automata.

This function is a wrapper which select a realtime 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_realtime() algorithm.

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

See also:
krat_exp_realtime.hh, realtime.hh

void realtime_here (  Element< S, T > &  e  ) 
 

Calls the do_realtime_here function for rational expression or automata.

This function is a wrapper which select a realtime either from realtime.hh or from krat_exp_realtime.hh.

It behaves exactly as realtime(), but do the operation in place.

See also:
realtime()

bool is_realtime (  const Element< S, T > &  e  ) 
 

Test whether an automaton or a regular expression is realtime.

This function returns true if the input is realtime.

Parameters:
e The automaton or regular expression to test.
See also:
realtime()

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.

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.

Parameters:
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.
Authors:
Thomas Claveirole <thomas@lrde.epita.fr>

Bug:
Multiple implementations of search() should be implemented. When a call to search is performed an heuristic should decide which implementation to use. For the moment there is no such mechanism since only one implementation of search is provided.

unsigned int compute_distances (  const Element< Automata< Series >, T > &  a,
std::vector< StatesSet > &  distances
)  [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.

std::pair<bool, unsigned int> window_backsearch (  const utility::Window< InputIterator, typename Element< Automata< Series >, T >::letter_t > &  w,
const Element< Automata< Series >, T > &  a,
const std::vector< StatesSet > &  distances
)  [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.

Parameters:
w The window.
a The automaton to use.
distances Distances get from compute_distances().
See also:
search(), build_reverse_factor_automaton(), compute_distances()

void standardize (  Element< A, T > &  a  ) 
 

Returns a standard automaton associated to the input.

Parameters:
a The automaton to standardize
See also:
is_standard()

Bug:
Not implemented yed

bool is_standard (  const Element< A, T > &  a  ) 
 

Returns true if the input automaton is standard.

Parameters:
a The automaton to test
See also:
standardize()

void union_of_standard_here (  Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

In-place union of two standard automata.

This function make the union of two standard automata. The result is a standard automaton.

Parameters:
lhs The first automaton (will contain the result)
rhs The second automaton
See also:
standardize(), is_standard(), union_of_standard()

Element< A, T > union_of_standard (  const Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

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.

Parameters:
lhs The first automaton
rhs The second automaton
See also:
standardize(), is_standard(), union_of_standard_here()

void concat_of_standard_here (  Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

In-place concatenation of two standard automata.

This function make the concatenation of two standard automata. The result is a standard automaton.

Parameters:
lhs The first automaton (will contain the result)
rhs The second automaton
See also:
standardize(), is_standard(), concat_of_standard()

Element< A, T > concat_of_standard (  const Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

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.

Parameters:
lhs The first automaton
rhs The second automaton
See also:
standardize(), is_standard(), concat_of_standard_here()

void star_of_standard_here (  Element< A, T > &  a  ) 
 

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.

Parameters:
a The automaton to transform
See also:
standardize(), is_standard(), star_of_standard()

Element< A, T > star_of_standard (  const Element< A, T > &  a  ) 
 

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.

Parameters:
a The automaton on which star must be applied.
See also:
standardize(), is_standard(), star_of_standard_here()

void standard_of (  Element< A, T > &  a,
const Exp &  e
) 
 

Convert a rational expression into a standard automaton.

Parameters:
e The expression to convert.
a The automaton to store the result.
Note:
The automaton is used to enable the use of different series from the expression.

Element< A, T > standard_of (  const Exp &  e  ) 
 

Convert a rational expression into a standard automaton.

Parameters:
e The expression to convert.
Returns:
A standard automaton.
Note:
The automaton is defined using the series of the expression.

Element< A, T > sub_automaton (  const Element< A, T > &  a,
const StatesSet &  s,
bool  check_states = true
) 
 

Returns a fresh automaton that is the sub-automaton defined by a set.

Parameters:
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.
Returns:
A fresh sub-automaton.
See also:
sub_automaton_here()

void sub_automaton_here (  Element< A, T > &  a,
const StatesSet &  s,
bool  check_states = true
) 
 

Select a sub-automaton into a given automaton.

Parameters:
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.
See also:
sub_automaton()

void sum_here (  Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

In place summing of two automata.

This function adds states and edges of an automaton to states and edges of a second automaton.

Parameters:
lhs Destination of the summing
rhs Source of summing
See also:
sum()

Element< A, T > sum (  const Element< A, T > &  lhs,
const Element< A, U > &  rhs
) 
 

Summing of two automata.

This function returns the fresh union of two automata. It put edges and states of the two automata together, and create a news one with the result.

Parameters:
lhs First automaton to sum
rhs Second automaton to sum
See also:
sum_here()

void thompson_of (  Element< A, T > &  out,
const rat::exp< Letter, Weight > &  kexp
) 
 

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.

Parameters:
out The resulting automaton
kexp The rational expression

Element< Automata< S >, AutoType > thompson_of (  const Element< S, T > &  exp  ) 
 

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.

Parameters:
exp The rational expression

void transpose (  lhs_t &  dst,
const rhs_t &  from
) 
 

Transposition of an automaton.

This function copy in dst the transposition of the automaton from.

Parameters:
from Automaton to transpose
dst Destination

auto_t transpose (  const auto_t &  from  ) 
 

Return a fresh transposed automaton.

This function returns the transposition of an automaton.

Parameters:
from Automaton to transpose.

Generated on Mon Mar 29 15:42:43 2004 for Vaucanson by doxygen 1.3.6-20040222