algos.hh File Reference

#include <iosfwd>
#include <string>
#include <vector>
#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:

Go to the source code of this file.

Namespaces
	vcsn
	vcsn::dyn
	FIXME: duplicate code with determinize.

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 define the same language. More...
bool	vcsn::dyn::are_equivalent (const ratexp &lhs, const ratexp &rhs)
	Whether define the same language. 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::blind (automaton &aut, unsigned tape)
	Focus on a specific tape of a tupleset automaton. More...
automaton	vcsn::dyn::cerny (const context &ctx, unsigned num_states)
	Produce a Černý automaton of num_states states. More...
automaton	vcsn::dyn::chain (const automaton &aut, int min, int max)
	Repeated concatenation of aut with itself. More...
ratexp	vcsn::dyn::chain (const ratexp &e, int min, int max)
	Repeated concatenation of e with itself. More...
automaton	vcsn::dyn::coaccessible (const automaton &aut)
	The coaccessible subautomaton of aut. More...
automaton	vcsn::dyn::complement (const automaton &aut)
	The complement of aut. More...
ratexp	vcsn::dyn::complement (const ratexp &r)
	Add the complement operator to r. More...
automaton	vcsn::dyn::complete (const automaton &aut)
	A completed copy of aut. More...
automaton	vcsn::dyn::compose (automaton &lhs, automaton &rhs)
	The composition of transducers lhs and rhs. More...
automaton	vcsn::dyn::concatenate (const automaton &lhs, const automaton &rhs)
	Concatenate two standard automata. More...
polynomial	vcsn::dyn::concatenate (const polynomial &lhs, const polynomial &rhs)
	Concatenate two polynomials. More...
ratexp	vcsn::dyn::concatenate (const ratexp &lhs, const ratexp &rhs)
	Concatenate two ratexps. More...
ratexp	vcsn::dyn::conjunction (const ratexp &lhs, const ratexp &rhs)
	The Hadamard product of ratexps lhs and rhs. More...
weight	vcsn::dyn::constant_term (const ratexp &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 ratexp &r)
	The context of this ratexp. 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...
ratexp	vcsn::dyn::copy (const ratexp &exp, const ratexpset &rs)
	Copy of exp, but built with rs. More...
automaton	vcsn::dyn::costandard (const automaton &a)
	A standardized transpositive a. More...
automaton	vcsn::dyn::de_bruijn (const context &ctx, unsigned n)
	A simple NFA for (a+b)*a(a+b)^n. More...
polynomial	vcsn::dyn::derivation (const ratexp &exp, const label &l, bool breaking=false)
	Derive exp with respect to s. More...
automaton	vcsn::dyn::derived_term (const ratexp &e, const std::string &algo="auto")
	The derived-term automaton of e. More...
automaton	vcsn::dyn::determinize (const automaton &aut, const std::string &algo="weighted")
	The determinized automaton. More...
automaton	vcsn::dyn::codeterminize (const automaton &aut, const std::string &algo="weighted")
	The codeterminized automaton. More...
automaton	vcsn::dyn::cominimize (const automaton &aut, const std::string &algo="auto")
	The cominimized 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...
ratexp	vcsn::dyn::difference (const ratexp &lhs, const ratexp &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...
std::ostream &	vcsn::dyn::dot (const automaton &aut, std::ostream &out, bool dot2tex=false)
	Output aut in GraphViz' Dot format. More...
std::string	vcsn::dyn::dot (const automaton &aut)
	A string representing aut in GraphViz' Dot format. 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)
	The LAO automaton aut with state s removed. More...
std::ostream &	vcsn::dyn::efsm (const automaton &aut, std::ostream &out)
	Output in Extended FSM format. More...
polynomial	vcsn::dyn::enumerate (const automaton &aut, unsigned max)
	All the accepted words of at most max letters. More...
weight	vcsn::dyn::eval (const automaton &aut, const label &l)
	Evaluate s on aut. More...
ratexp	vcsn::dyn::expand (const ratexp &e)
	Distribute product over addition recursively under the starred subexpressions and group the equal monomials. More...
automaton	vcsn::dyn::factor (const automaton &aut)
	Create a factor automaton from aut. More...
std::ostream &	vcsn::dyn::fado (const automaton &aut, std::ostream &out)
	Output in FAdo format. 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...
std::ostream &	vcsn::dyn::grail (const automaton &aut, std::ostream &out)
	Output in Grail format. More...
bool	vcsn::dyn::has_twins_property (const automaton &aut)
	Whether the automaton has the twins property. More...
rat::identities	vcsn::dyn::identities (const ratexp &exp)
	The identities of ratexp 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...
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 ratexp &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_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_standard (const automaton &aut)
	Whether is standard (unique initial state, with weight one, no incoming transition). 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 ratexp &e)
	Whether rational expression is valid (all the starred sub-expressions are starrable). More...
automaton	vcsn::dyn::minimize (const automaton &aut, const std::string &algo="auto")
	The minimized automaton. More...
automaton	vcsn::dyn::ladybird (const context &ctx, unsigned n)
	The ladybird automaton with n states. More...
automaton	vcsn::dyn::left_mult (const weight &w, const automaton &aut)
	The left-multiplication of an automaton with w as weight. More...
ratexp	vcsn::dyn::left_mult (const weight &w, const ratexp &aut)
	The left-multiplication of a ratexp with w as weight. More...
automaton	vcsn::dyn::lift (const automaton &aut)
	The lifted LAO automaton from aut. More...
ratexp	vcsn::dyn::lift (const ratexp &e)
	The lifted LAO rational expression from e. 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...
ratexpset	vcsn::dyn::make_ratexpset (const context &ctx,::vcsn::rat::identities is)
	Build an ratexpset from its context. More...
context	vcsn::dyn::make_word_context (const context &ctx)
	The context for words. More...
weight	vcsn::dyn::multiply (const weight &lhs, const weight &rhs)
	Multiply two weights. More...
automaton	vcsn::dyn::normalize (const automaton &aut)
	Normalize automaton aut. More...
automaton	vcsn::dyn::pair (const automaton &aut, bool keep_initials=false)
	Build the pair automaton of the given automaton. More...
automaton	vcsn::dyn::prefix (const automaton &aut)
	Create a prefix automaton from aut. More...
automaton	vcsn::dyn::power (const automaton &aut, unsigned n)
	Repeated product of aut with itself. More...
std::ostream &	vcsn::dyn::print (const automaton &a, std::ostream &o, 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 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 ratexp &e, std::ostream &o, const std::string &format="default")
	Print ratexp e 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::product (const automaton &lhs, const automaton &rhs)
	The product of automata lhs and rhs. More...
automaton	vcsn::dyn::product (const std::vector< automaton > &as)
	The product of automata. More...
automaton	vcsn::dyn::proper (const automaton &aut, direction dir=direction::backward, bool prune=true)
	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)
	Produce a random automaton. More...
automaton	vcsn::dyn::random_automaton_deterministic (const context &ctx, unsigned num_states)
	Produce a random deterministic automaton. More...
automaton	vcsn::dyn::read_automaton (std::istream &is, const std::string &format="default")
	Read an automaton from a stream. More...
label	vcsn::dyn::read_label (std::istream &is, const context &ctx)
	Read a label from a stream. More...
ratexp	vcsn::dyn::read_ratexp (std::istream &is, const ratexpset &rs, const std::string &format="default")
	Read a ratexp from a stream. More...
polynomial	vcsn::dyn::read_polynomial (std::istream &is, const context &ctx)
	Read a polynomial from a stream. More...
weight	vcsn::dyn::read_weight (std::istream &is, const context &ctx)
	Read a weight from a stream. 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...
ratexp	vcsn::dyn::right_mult (const ratexp &aut, const weight &w)
	The right-multiplication of a ratexp with w as weight. More...
std::size_t	vcsn::dyn::num_sccs (const automaton &aut)
	The number of strongly connected components. More...
polynomial	vcsn::dyn::shortest (const automaton &aut, unsigned max=1)
	The at-most max first accepted words. 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...
ratexp	vcsn::dyn::shuffle (const ratexp &lhs, const ratexp &rhs)
	The shuffle product of ratexps 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 polynomial &p)
	Break all the expressions in p. More...
polynomial	vcsn::dyn::split (const ratexp &exp)
	Break exp. More...
automaton	vcsn::dyn::standard (const automaton &a)
	A standardized a. More...
automaton	vcsn::dyn::standard (const ratexp &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 ratexp &rs)
	Star height of a ratexp. More...
ratexp	vcsn::dyn::star_normal_form (const ratexp &e)
	A normalized form where star is applied only to expression without null constant-term. 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...
polynomial	vcsn::dyn::sum (const polynomial &lhs, const polynomial &rhs)
	Sum of two polynomials. More...
ratexp	vcsn::dyn::sum (const ratexp &lhs, const ratexp &rhs)
	Sum of two ratexps. More...
weight	vcsn::dyn::sum (const weight &lhs, const weight &rhs)
	Sum of two weights. 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 ratexp &e)
	The Thompson automaton of e. More...
std::ostream &	vcsn::dyn::tikz (const automaton &aut, std::ostream &out)
	Output aut in LaTeX's TikZ format. More...
expansion	vcsn::dyn::to_expansion (const ratexp &exp)
	First order development of a exp. More...
ratexp	vcsn::dyn::to_expression (const automaton &aut, const std::string &algo="auto")
	A ratexp denoting the language of aut. More...
automaton	vcsn::dyn::transpose (automaton &aut)
	Transpose aut. More...
ratexp	vcsn::dyn::transpose (const ratexp &e)
	Transpose e. More...
ratexp	vcsn::dyn::transposition (const ratexp &r)
	Add the transposition operator to r. More...
automaton	vcsn::dyn::trim (const automaton &aut)
	The useful subautomaton of aut. 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...
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::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::ratexp &e)
	Output ratexp e on o. More...
std::ostream &	std::operator<< (std::ostream &o, const vcsn::dyn::weight &w)
	Output weight w on o. More...