Vcsn  2.4
Be Rational
algos.hh File Reference
#include <iosfwd>
#include <string>
#include <vector>
#include <boost/optional.hpp>
#include <vcsn/algos/fwd.hh>
#include <vcsn/ctx/fwd.hh>
#include <vcsn/dyn/fwd.hh>
#include <vcsn/dyn/types.hh>
#include <vcsn/misc/export.hh>
Include dependency graph for algos.hh:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces

 vcsn
 
 vcsn::dyn
 

Functions

automaton vcsn::dyn::accessible (const automaton &aut)
 The accessible subautomaton of aut. More...
 
word vcsn::dyn::ambiguous_word (const automaton &aut)
 An ambiguous word, or raise if there is none. More...
 
bool vcsn::dyn::are_equivalent (const automaton &lhs, const automaton &rhs)
 Whether compute the same series. More...
 
bool vcsn::dyn::are_equivalent (const expression &lhs, const expression &rhs)
 Whether denote the same series. More...
 
bool vcsn::dyn::are_isomorphic (const automaton &lhs, const automaton &rhs)
 Whether there exists an isomorphism between the states of lhs and those of rhs. More...
 
automaton vcsn::dyn::cerny (const context &ctx, unsigned num_states)
 Produce a Černý automaton of num_states states. More...
 
automaton vcsn::dyn::coaccessible (const automaton &aut)
 The coaccessible subautomaton of aut. More...
 
automaton vcsn::dyn::codeterminize (const automaton &aut, const std::string &algo="auto")
 The codeterminized automaton. More...
 
automaton vcsn::dyn::cominimize (const automaton &aut, const std::string &algo="auto")
 The cominimized automaton. More...
 
automaton vcsn::dyn::complement (const automaton &aut)
 The complement of aut. More...
 
expansion vcsn::dyn::complement (const expansion &x)
 Complement this expansion. More...
 
automaton vcsn::dyn::complete (const automaton &aut)
 A completed copy of aut. More...
 
automaton vcsn::dyn::component (const automaton &aut, unsigned num)
 The automaton of a strongly connected component. More...
 
automaton vcsn::dyn::compose (const automaton &lhs, const automaton &rhs, bool lazy=false)
 The composition of transducers lhs and rhs. More...
 
expansion vcsn::dyn::compose (const expansion &lhs, const expansion &rhs)
 The composition of two expansions. More...
 
expression vcsn::dyn::concatenate (const expression &lhs, const expression &rhs)
 Concatenate two expressions. More...
 
automaton vcsn::dyn::condense (const automaton &aut)
 The condensation of aut such that each state is a strongly connected component. More...
 
automaton vcsn::dyn::conjunction (const automaton &lhs, const automaton &rhs, bool lazy=false)
 The conjunction (aka synchronized product) of automata. More...
 
automaton vcsn::dyn::conjunction (const std::vector< automaton > &as, bool lazy=false)
 The conjunction (aka synchronized product) of automata. More...
 
automaton vcsn::dyn::conjunction (const automaton &aut, unsigned n)
 Repeated conjunction of aut with itself. More...
 
expansion vcsn::dyn::conjunction (const expansion &lhs, const expansion &rhs)
 The Hadamard product of expansions lhs and rhs. More...
 
automaton vcsn::dyn::conjugate (const automaton &aut)
 The conjugate of aut. More...
 
weight vcsn::dyn::constant_term (const expression &e)
 The weight associated to the empty word in e. More...
 
context vcsn::dyn::context_of (const automaton &a)
 The context of this automaton. More...
 
context vcsn::dyn::context_of (const expansion &r)
 The context of this expansion. More...
 
automaton vcsn::dyn::copy (const automaton &aut)
 A copy of aut. More...
 
automaton vcsn::dyn::copy (const automaton &aut, const context &ctx)
 A copy of aut converted to context ctx. More...
 
expression vcsn::dyn::copy (const expression &exp, const context &ctx, identities ids)
 Copy of exp, but built with ctx. More...
 
automaton vcsn::dyn::costandard (const automaton &a)
 A co-standardized a. More...
 
automaton vcsn::dyn::cotrie (const polynomial &p)
 A reversed trie-like automaton (multiple initial states, single final state) automaton to accept p. More...
 
automaton vcsn::dyn::cotrie (const context &ctx, std::istream &is, const std::string &format="default")
 A reversed trie-like automaton (multiple initial states, single final state) automaton to accept the series contained in is. More...
 
automaton vcsn::dyn::de_bruijn (const context &ctx, unsigned n)
 A simple NFA for (a+b)*a(a+b)^n. More...
 
automaton vcsn::dyn::delay_automaton (const automaton &a)
 The automaton with the delay of each state. More...
 
polynomial vcsn::dyn::derivation (const expression &exp, const label &lbl, bool breaking=false)
 Derive exp with respect to s. More...
 
automaton vcsn::dyn::derived_term (const expression &exp, const std::string &algo="auto")
 The derived-term automaton of exp. More...
 
automaton vcsn::dyn::determinize (const automaton &aut, const std::string &algo="auto")
 The determinized automaton. More...
 
automaton vcsn::dyn::difference (const automaton &lhs, const automaton &rhs)
 An automaton whose behavior is that of lhs on words not accepted by rhs. More...
 
expression vcsn::dyn::difference (const expression &lhs, const expression &rhs)
 Words accepted by lhs, but not by rhs. More...
 
automaton vcsn::dyn::divkbaseb (const context &ctx, unsigned divisor, unsigned base)
 An automaton which accepts a word n representing a number in base b iff k|n. More...
 
automaton vcsn::dyn::double_ring (const context &ctx, unsigned n, const std::vector< unsigned > &f)
 The double_ring automaton with n states and f the list of finals. More...
 
automaton vcsn::dyn::eliminate_state (const automaton &aut, int s=-1)
 The LAO automaton aut with state s removed. More...
 
weight vcsn::dyn::evaluate (const automaton &aut, const word &l)
 Evaluate l on aut. More...
 
expression vcsn::dyn::expand (const expression &e)
 Distribute product over addition recursively under the starred subexpressions and group the equal monomials. More...
 
expression vcsn::dyn::expression_one (const context &c, identities ids)
 The expression for \\e. More...
 
expression vcsn::dyn::expression_zero (const context &c, identities ids)
 The expression for \\z. More...
 
automaton vcsn::dyn::factor (const automaton &aut)
 Create a factor automaton from aut. More...
 
automaton vcsn::dyn::filter (const automaton &aut, const std::vector< unsigned > &ss)
 The subautomaton based on aut, with only states in ss visible. More...
 
automaton vcsn::dyn::focus (const automaton &aut, unsigned tape)
 Focus on a specific tape of a tupleset automaton. More...
 
bool vcsn::dyn::has_twins_property (const automaton &aut)
 Whether the automaton has the twins property. More...
 
bool vcsn::dyn::has_lightening_cycle (const automaton &aut)
 Whether the automaton has a cycle with lightening weight. More...
 
bool vcsn::dyn::has_bounded_lag (const automaton &aut)
 Whether the transducer has bounded lag. More...
 
identities vcsn::dyn::identities_of (const expression &exp)
 The identities of expression exp. More...
 
automaton vcsn::dyn::inductive (const expression &e, const std::string &algo="auto")
 The inductive translation of e in an automaton. More...
 
automaton vcsn::dyn::infiltrate (const automaton &lhs, const automaton &rhs)
 The infiltration of automata lhs and rhs. More...
 
automaton vcsn::dyn::infiltrate (const std::vector< automaton > &as)
 The infiltration product of automata. More...
 
expression vcsn::dyn::infiltrate (const expression &lhs, const expression &rhs)
 The infiltration product of expressions lhs and rhs. More...
 
std::ostream & vcsn::dyn::info (const automaton &aut, std::ostream &out=std::cout, unsigned details=2)
 Output various facts about an automaton. More...
 
std::ostream & vcsn::dyn::info (const expression &exp, std::ostream &out=std::cout)
 Output various facts about exp. More...
 
automaton vcsn::dyn::insplit (const automaton &aut, bool lazy=false)
 Split automaton on the incoming transition. More...
 
bool vcsn::dyn::is_accessible (const automaton &aut)
 Whether aut is accessible. More...
 
bool vcsn::dyn::is_ambiguous (const automaton &aut)
 Whether aut is ambiguous. More...
 
bool vcsn::dyn::is_coaccessible (const automaton &aut)
 Whether aut is coaccessible. More...
 
bool vcsn::dyn::is_codeterministic (const automaton &aut)
 Whether aut is codeterministic. More...
 
bool vcsn::dyn::is_complete (const automaton &aut)
 Whether aut is complete. More...
 
bool vcsn::dyn::is_costandard (const automaton &aut)
 Whether is costandard (unique final state, with weight one, no outcoming transition). More...
 
bool vcsn::dyn::is_cycle_ambiguous (const automaton &aut)
 Whether the automaton is cycle-ambiguous. More...
 
bool vcsn::dyn::is_deterministic (const automaton &aut)
 Whether aut is deterministic. More...
 
bool vcsn::dyn::is_empty (const automaton &aut)
 Whether has no state. More...
 
bool vcsn::dyn::is_eps_acyclic (const automaton &aut)
 Whether has no cycle of spontaneous transitions. More...
 
bool vcsn::dyn::is_functional (const automaton &aut)
 Whether aut is functional. More...
 
bool vcsn::dyn::is_letterized (const automaton &aut)
 Whether aut is letterized. More...
 
bool vcsn::dyn::is_partial_identity (const automaton &aut)
 Whether aut realizes a partial identity. More...
 
bool vcsn::dyn::is_normalized (const automaton &aut)
 Whether is normalized (in the Thompson sense), i.e., standard and co-standard. More...
 
bool vcsn::dyn::is_out_sorted (const automaton &aut)
 Whether the outgoing transitions of each state have increasing labels. More...
 
bool vcsn::dyn::is_proper (const automaton &aut)
 Whether has no spontaneous transition. More...
 
bool vcsn::dyn::is_realtime (const automaton &aut)
 Whether has no spontaneous transition, and is letterized. More...
 
bool vcsn::dyn::is_standard (const automaton &aut)
 Whether is standard (unique initial state, with weight one, no incoming transition). More...
 
bool vcsn::dyn::is_synchronized (const automaton &aut)
 Whether is synchronized. More...
 
bool vcsn::dyn::is_synchronized_by (const automaton &aut, const word &word)
 Whether the word synchronizes aut. More...
 
bool vcsn::dyn::is_synchronizing (const automaton &aut)
 Whether is synchronizing. More...
 
bool vcsn::dyn::is_trim (const automaton &aut)
 Whether has no useless state. More...
 
bool vcsn::dyn::is_useless (const automaton &aut)
 Whether has no useful state. More...
 
bool vcsn::dyn::is_valid (const automaton &e)
 Whether automaton is valid (epsilon-cycles converge). More...
 
bool vcsn::dyn::is_valid (const expression &e)
 Whether rational expression is valid (all the starred sub-expressions are starrable). More...
 
context vcsn::dyn::join (const context &lhs, const context &rhs)
 The join between two contexts, i.e., their lowest common supertype. More...
 
automaton vcsn::dyn::ladybird (const context &ctx, unsigned n)
 The ladybird automaton with n states. More...
 
automaton vcsn::dyn::ldivide (const automaton &lhs, const automaton &rhs)
 Left-division of two automata (lhs \ rhs). More...
 
expansion vcsn::dyn::ldivide (const expansion &lhs, const expansion &rhs)
 Left-division of two expansions (lhs \ rhs). More...
 
polynomial vcsn::dyn::lgcd (const polynomial &lhs, const polynomial &rhs)
 Left greatest common divisor of two polynomials (lhs \ rhs). More...
 
automaton vcsn::dyn::lweight (const weight &w, const automaton &aut, const std::string &algo="auto")
 The left-multiplication of an automaton with w as weight. More...
 
expansion vcsn::dyn::lweight (const weight &w, const expansion &exp)
 The left-multiplication of an expansion with w as weight. More...
 
bool vcsn::dyn::less_than (const expression &lhs, const expression &rhs)
 Ordering between expressions. More...
 
automaton vcsn::dyn::letterize (const automaton &aut)
 The automaton with letter transitions instead of words. More...
 
automaton vcsn::dyn::levenshtein (const context &ls)
 The transducer representing the Levenshtein distance. More...
 
automaton vcsn::dyn::lift (const automaton &aut, const std::vector< unsigned > &tapes={}, identities ids={})
 Lift some tapes of the transducer, or turn an automaton into a spontaneous automaton. More...
 
expression vcsn::dyn::lift (const expression &e)
 The lifted LAO rational expression from e. More...
 
polynomial vcsn::dyn::lightest (const automaton &aut, unsigned num=1, const std::string &algo="auto")
 The approximated behavior of an automaton with smallest weights. More...
 
automaton vcsn::dyn::lightest_automaton (const automaton &aut, unsigned num=1, const std::string &algo="auto")
 The shortest path automaton using the given algorithm. More...
 
context vcsn::dyn::make_context (const std::string &name)
 Build a context from its name. More...
 
automaton_editor * vcsn::dyn::make_automaton_editor (const context &ctx)
 Build an automatonset from its context. More...
 
context vcsn::dyn::make_word_context (const context &ctx)
 The context for words. More...
 
automaton vcsn::dyn::multiply (const automaton &lhs, const automaton &rhs, const std::string &algo="auto")
 Multiply (concatenate) two automata. More...
 
automaton vcsn::dyn::multiply (const automaton &aut, int min, int max=-2, const std::string &algo="auto")
 Repeated multiplication (concatenation) of an automaton with itself. More...
 
expression vcsn::dyn::multiply (const expression &lhs, const expression &rhs)
 Multiply (concatenate) two expressions. More...
 
expression vcsn::dyn::multiply (const expression &e, int min, int max=-2)
 Repeated multiplication (concatenation) of an expression with itself. More...
 
label vcsn::dyn::multiply (const label &l, int num)
 Repeated multiplication of a label with itself. More...
 
automaton vcsn::dyn::minimize (const automaton &aut, const std::string &algo="auto")
 The minimized automaton. More...
 
automaton vcsn::dyn::normalize (const automaton &aut)
 Normalize automaton aut. More...
 
std::size_t vcsn::dyn::num_components (const automaton &aut)
 The number of strongly connected components. More...
 
std::size_t vcsn::dyn::num_tapes (const context &ctx)
 The number of input tapes. More...
 
automaton vcsn::dyn::pair (const automaton &aut, bool keep_initials=false)
 Build the pair automaton of the given automaton. More...
 
automaton vcsn::dyn::partial_identity (const automaton &aut)
 Create a partial identity transducer from aut. More...
 
expression vcsn::dyn::partial_identity (const expression &e)
 Create a partial-identity two-tape expression from e. More...
 
automaton vcsn::dyn::prefix (const automaton &aut)
 Create a prefix automaton from aut. More...
 
std::ostream & vcsn::dyn::print (const automaton &aut, std::ostream &out=std::cout, const std::string &format="default")
 Print automaton a on out using format format. More...
 
std::ostream & vcsn::dyn::print (const context &c, std::ostream &out=std::cout, const std::string &format="default")
 Print context c on out using format format. More...
 
std::ostream & vcsn::dyn::print (const expansion &e, std::ostream &out=std::cout, const std::string &format="default")
 Print expansion e on out using format format. More...
 
automaton vcsn::dyn::quotkbaseb (const context &ctx, unsigned divisor, unsigned base)
 A transducer that computes the quotient of the division of a word n by k in base b iff k|n. More...
 
void vcsn::dyn::set_format (std::ostream &out, const std::string &format)
 Specify the output format for out. More...
 
std::string vcsn::dyn::get_format (std::ostream &out)
 Get the output format for out. More...
 
automaton vcsn::dyn::project (const automaton &aut, unsigned tape)
 Keep a single tape from a multiple-tape automaton. More...
 
context vcsn::dyn::project (const context &ctx, unsigned tape)
 Keep a single tape from a multiple-tape context. More...
 
expansion vcsn::dyn::project (const expansion &xpn, unsigned tape)
 Keep a single tape from a multiple-tape expansion. More...
 
automaton vcsn::dyn::proper (const automaton &aut, direction dir=direction::backward, bool prune=true, const std::string &algo="auto")
 An equivalent automaton without spontaneous transitions. More...
 
automaton vcsn::dyn::push_weights (const automaton &aut)
 The weight pushing automaton of aut. More...
 
automaton vcsn::dyn::random_automaton (const context &ctx, unsigned num_states, float density=0.1, unsigned num_initial=1, unsigned num_final=1, boost::optional< unsigned > max_labels={}, float loop_chance=0.0, const std::string &weights="")
 A random automaton. More...
 
automaton vcsn::dyn::random_automaton_deterministic (const context &ctx, unsigned num_states)
 A random deterministic automaton. More...
 
expression vcsn::dyn::random_expression (const context &ctx, const std::string &param="+, ., *=.2, w., .w, length=10", identities ids={})
 A random expression. More...
 
weight vcsn::dyn::random_weight (const context &ctx, const std::string &param)
 A random weight. More...
 
automaton vcsn::dyn::rdivide (const automaton &lhs, const automaton &rhs)
 Right-division of two automata (lhs / rhs). More...
 
expression vcsn::dyn::rdivide (const expression &lhs, const expression &rhs)
 Right-division of two expressions (lhs / rhs). More...
 
automaton vcsn::dyn::read_automaton (std::istream &is, const std::string &format="default", bool strip=true)
 Read an automaton from a stream. More...
 
expression vcsn::dyn::read_expression (const context &ctx, identities ids, std::istream &is, const std::string &format="default")
 Read an expression from a stream. More...
 
label vcsn::dyn::read_label (const context &ctx, std::istream &is, const std::string &format="default")
 Read a label from a stream. More...
 
polynomial vcsn::dyn::read_polynomial (const context &ctx, std::istream &is)
 Read a polynomial from a stream. More...
 
weight vcsn::dyn::read_weight (const context &ctx, std::istream &is)
 Read a weight from a stream. More...
 
automaton vcsn::dyn::realtime (const automaton &aut)
 Create the realtime automaton (letterized and proper). More...
 
automaton vcsn::dyn::reduce (const automaton &aut)
 Reduce aut. More...
 
automaton vcsn::dyn::rweight (const automaton &aut, const weight &w, const std::string &algo="auto")
 The right-mult automaton with w as weight. More...
 
expansion vcsn::dyn::rweight (const expansion &aut, const weight &w)
 The right-multiplication of an expansion with w as weight. More...
 
automaton vcsn::dyn::scc (const automaton &aut, const std::string &algo="auto")
 Build the SCC automaton whose states are labeled with number of the strongly-connected component they belong to. More...
 
polynomial vcsn::dyn::shortest (const automaton &aut, boost::optional< unsigned > num={}, boost::optional< unsigned > len={})
 The approximated behavior of an automaton. More...
 
automaton vcsn::dyn::shuffle (const automaton &lhs, const automaton &rhs)
 The shuffle product of automata lhs and rhs. More...
 
automaton vcsn::dyn::shuffle (const std::vector< automaton > &as)
 The shuffle product of automata. More...
 
expression vcsn::dyn::shuffle (const expression &lhs, const expression &rhs)
 The shuffle product of expressions lhs and rhs. More...
 
automaton vcsn::dyn::sort (const automaton &a)
 A copy of a with normalized state numbers. More...
 
polynomial vcsn::dyn::split (const expression &exp)
 Break exp. More...
 
automaton vcsn::dyn::standard (const automaton &a)
 A standardized a. More...
 
automaton vcsn::dyn::standard (const expression &e)
 The standard automaton of e. More...
 
automaton vcsn::dyn::star (const automaton &aut, const std::string &algo="auto")
 Star of an automaton. More...
 
unsigned vcsn::dyn::star_height (const expression &rs)
 Star height of an expression. More...
 
expression vcsn::dyn::star_normal_form (const expression &e)
 A normalized form where star is applied only to proper expressions. More...
 
automaton vcsn::dyn::strip (const automaton &a)
 The automaton in a with its metadata layers removed. More...
 
automaton vcsn::dyn::suffix (const automaton &aut)
 Create a suffix automaton from aut. More...
 
automaton vcsn::dyn::subword (const automaton &aut)
 Create a subword automaton from aut. More...
 
automaton vcsn::dyn::add (const automaton &lhs, const automaton &rhs, const std::string &algo="auto")
 Sum of two automata. More...
 
expression vcsn::dyn::add (const expression &lhs, const expression &rhs)
 Sum of two expressions. More...
 
automaton vcsn::dyn::synchronize (const automaton &aut)
 Create a synchronized transducer from aut. More...
 
word vcsn::dyn::synchronizing_word (const automaton &aut, const std::string &algo="greedy")
 A synchronizing word, or raise if there is none. More...
 
automaton vcsn::dyn::thompson (const expression &e)
 The Thompson automaton of e. More...
 
automaton vcsn::dyn::to_automaton (const expression &exp, const std::string &algo="auto")
 An automaton denoting the language of exp. More...
 
expansion vcsn::dyn::to_expansion (const expression &exp)
 First order development of a exp. More...
 
expression vcsn::dyn::to_expression (const automaton &aut, identities ids={}, const std::string &algo="auto")
 An expression denoting the language of aut. More...
 
expression vcsn::dyn::to_expression (const context &ctx, identities ids, const label &l)
 An expression denoting the label of l. More...
 
expression vcsn::dyn::to_expression (const context &ctx, identities ids, const letter_class_t &letters, bool accept=true)
 An expression matching one letter in a letter class. More...
 
automaton vcsn::dyn::transpose (automaton &aut)
 Transpose aut. More...
 
expression vcsn::dyn::transpose (const expression &e)
 Transpose e. More...
 
expression vcsn::dyn::transposition (const expression &r)
 Add the transposition operator to r. More...
 
automaton vcsn::dyn::trie (const polynomial &p)
 A trie-like automaton (single initial state, multiple final states) to accept p. More...
 
automaton vcsn::dyn::trie (const context &ctx, std::istream &is, const std::string &format="default")
 A trie-like automaton (single initial state, multiple final states) to accept the series contained in is. More...
 
automaton vcsn::dyn::trim (const automaton &aut)
 The trim subautomaton of aut. More...
 
automaton vcsn::dyn::tuple (const automaton &lhs, const automaton &rhs)
 Build a two-tape automaton from two automata. More...
 
automaton vcsn::dyn::tuple (const std::vector< automaton > &as)
 Build a k-tape automaton from k automata. More...
 
context vcsn::dyn::tuple (const context &lhs, const context &rhs)
 Tuple two contexts. More...
 
context vcsn::dyn::tuple (const std::vector< context > &ctxs)
 A k-tape context from k contexts. More...
 
expansion vcsn::dyn::tuple (const std::vector< expansion > &rs)
 Build a k-tape expansion from k expansions. More...
 
expression vcsn::dyn::tuple (const expression &lhs, const expression &rhs)
 Build a two-tape expression from two expressions. More...
 
std::string vcsn::dyn::type (const automaton &a)
 The implementation type of a. More...
 
automaton vcsn::dyn::u (const context &ctx, unsigned n)
 The Brzozowski universal witness. More...
 
automaton vcsn::dyn::universal (const automaton &aut)
 The universal automaton of aut. More...
 
weight vcsn::dyn::weight_one (const context &c)
 The weight one. More...
 
weight vcsn::dyn::weight_series (const automaton &aut)
 Compute weight of the series. More...
 
weight vcsn::dyn::weight_zero (const context &c)
 The weight zero. More...
 
automaton vcsn::dyn::zpc (const expression &exp, const std::string &algo="auto")
 The ZPC automaton of exp. More...
 
std::ostream & vcsn::dyn::operator<< (std::ostream &o, const automaton &a)
 Output automaton a on o. More...
 
std::ostream & vcsn::dyn::operator<< (std::ostream &o, const context &c)
 Output context c on o. More...
 
std::ostream & vcsn::dyn::operator<< (std::ostream &o, const expansion &e)
 Output expansion e on o. More...