algos.hh File Reference

#include <iosfwd>
#include <string>
#include <vector>
#include <boost/optional.hpp>
#include <vcsn/algos/fwd.hh>
#include <vcsn/core/rat/identities.hh>
#include <vcsn/ctx/fwd.hh>
#include <vcsn/dyn/fwd.hh>
#include <vcsn/misc/direction.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...
label	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...
expression	vcsn::dyn::complement (const expression &r)
	Add the complement operator to r. 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 (automaton &lhs, automaton &rhs)
	The composition of transducers lhs and rhs. 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...
expression	vcsn::dyn::conjunction (const expression &lhs, const expression &rhs)
	The Hadamard product of expressions lhs and rhs. 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 expression &r)
	The context of this expression. 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, rat::identities ids)
	Copy of exp, but built with ctx. More...
automaton	vcsn::dyn::costandard (const automaton &a)
	A standardized transpositive 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)
	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::eval (const automaton &aut, const label &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, rat::identities ids)
	The expression for \e. More...
expression	vcsn::dyn::expression_zero (const context &c, rat::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_bounded_lag (const automaton &aut)
	Whether the transducer has bounded lag. More...
rat::identities	vcsn::dyn::identities (const expression &exp)
	The identities of expression exp. More...
automaton	vcsn::dyn::infiltration (const automaton &lhs, const automaton &rhs)
	The infiltration of automata lhs and rhs. More...
automaton	vcsn::dyn::infiltration (const std::vector< automaton > &as)
	The infiltration product of automata. More...
expression	vcsn::dyn::infiltration (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, bool detailed=false)
	Output various facts about an automaton. More...
std::ostream &	vcsn::dyn::info (const expression &exp, std::ostream &out)
	Output various facts about exp. More...
automaton	vcsn::dyn::insplit (const automaton &aut)
	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 label &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...
polynomial	vcsn::dyn::ldiv (const polynomial &lhs, const polynomial &rhs)
	Left-division of two polynomials (lhs \ rhs). More...
expression	vcsn::dyn::ldiv (const expression &lhs, const expression &rhs)
	Left-division of two expressions (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::left_mult (const weight &w, const automaton &aut)
	The left-multiplication of an automaton with w as weight. More...
expression	vcsn::dyn::left_mult (const weight &w, const expression &exp)
	The left-multiplication of an expression 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={}, rat::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, boost::optional< unsigned > num={})
	The approximated behavior of an automaton with smallest weights. 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)
	Multiply (concatenate) two standard automata. More...
automaton	vcsn::dyn::multiply (const automaton &aut, int min, int max)
	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)
	Repeated multiplication (concatenation) of an expression with itself. More...
label	vcsn::dyn::multiply (const label &lhs, const label &rhs)
	Multiply (concatenate) two labels. More...
polynomial	vcsn::dyn::multiply (const polynomial &lhs, const polynomial &rhs)
	Multiply two polynomials. More...
weight	vcsn::dyn::multiply (const weight &lhs, const weight &rhs)
	Multiply two weights. More...
weight	vcsn::dyn::multiply (const weight &e, int min, int max)
	Repeated multiplication of a weight 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...
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, const std::string &format="default")
	Print automaton a on o using format format. More...
std::ostream &	vcsn::dyn::print (const context &c, std::ostream &o, const std::string &format="default")
	Print context c on o using format format. More...
std::ostream &	vcsn::dyn::print (const expansion &e, std::ostream &o, const std::string &format="default")
	Print expansion e on o using format format. More...
std::ostream &	vcsn::dyn::print (const expression &e, std::ostream &o, const std::string &format="default")
	Print expression e on o using format format. More...
std::ostream &	vcsn::dyn::print (const label &l, std::ostream &o, const std::string &format="default")
	Print label l on o using format format. More...
std::ostream &	vcsn::dyn::print (const polynomial &p, std::ostream &o, const std::string &format="default")
	Print polynomial p on o using format format. More...
std::ostream &	vcsn::dyn::print (const weight &w, std::ostream &o, const std::string &format="default")
	Print weight w on o using format format. More...
void	vcsn::dyn::set_format (std::ostream &o, const std::string &format)
	Specify the output format for o. More...
std::string	vcsn::dyn::get_format (std::ostream &o)
	Get the output format for o. 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...
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, float loop_chance=0.0)
	Produce a random automaton. More...
automaton	vcsn::dyn::random_automaton_deterministic (const context &ctx, unsigned num_states)
	Produce a random deterministic automaton. More...
expression	vcsn::dyn::rdiv (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, rat::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::right_mult (const automaton &aut, const weight &w)
	The right-mult automaton with w as weight. More...
expression	vcsn::dyn::right_mult (const expression &aut, const weight &w)
	The right-multiplication of an expression 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...
polynomial	vcsn::dyn::split (const polynomial &p)
	Break all the expressions in p. 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)
	Star of a standard 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::sum (const automaton &lhs, const automaton &rhs)
	Sum of two standard automata. More...
expression	vcsn::dyn::sum (const expression &lhs, const expression &rhs)
	Sum of two expressions. More...
polynomial	vcsn::dyn::sum (const polynomial &lhs, const polynomial &rhs)
	Sum of two polynomials. More...
weight	vcsn::dyn::sum (const weight &lhs, const weight &rhs)
	Sum of two weights. More...
automaton	vcsn::dyn::synchronize (const automaton &aut)
	Create a synchronized transducer from aut. More...
label	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, rat::identities ids={}, const std::string &algo="auto")
	An expression denoting the language of aut. More...
expression	vcsn::dyn::to_expression (const context &ctx, rat::identities ids, const label &l)
	An expression denoting the label of l. More...
expression	vcsn::dyn::to_expression (const context &ctx, rat::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)
	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...
expression	vcsn::dyn::tuple (const expression &lhs, const expression &rhs)
	Build a two-tape expression from two expressions. More...
expression	vcsn::dyn::tuple (const std::vector< expression > &rs)
	Build a k-tape expression from k 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::union_a (const automaton &lhs, const automaton &rhs)
	Union of two automata (plain graph union). More...
automaton	vcsn::dyn::universal (const automaton &aut)
	The universal automaton of aut. More...
weight	vcsn::dyn::weight_series (const automaton &aut)
	Compute weight of the series. More...
automaton	vcsn::dyn::zpc (const expression &exp, const std::string &algo="auto")
	The ZPC automaton of exp. More...
std::ostream &	std::operator<< (std::ostream &o, const vcsn::dyn::automaton &a)
	Output automaton a on o. More...
std::ostream &	std::operator<< (std::ostream &o, const vcsn::dyn::context &c)
	Output context c on o. More...
std::ostream &	std::operator<< (std::ostream &o, const vcsn::dyn::expansion &e)
	Output expansion e on o. More...
std::ostream &	std::operator<< (std::ostream &o, const vcsn::dyn::expression &r)
	Output expression r on o. More...
std::ostream &	std::operator<< (std::ostream &o, const vcsn::dyn::label &l)
	Output label l on o. More...
std::ostream &	std::operator<< (std::ostream &o, const vcsn::dyn::polynomial &p)
	Output polynomial p on o. More...
std::ostream &	std::operator<< (std::ostream &o, const vcsn::dyn::weight &w)
	Output weight w on o. More...