7 #include <boost/optional.hpp>
9 #include <vcsn/algos/fwd.hh>
56 const std::string& algo =
"auto");
65 const std::string& algo =
"auto");
168 bool breaking =
false);
180 const std::string& algo =
"auto");
192 const std::string& algo =
"auto");
211 const std::vector<unsigned>& f);
267 bool detailed =
false);
410 const std::vector<unsigned>& tapes = {},
421 boost::optional<unsigned> num = {});
475 const std::string& algo =
"auto");
509 const std::string& format =
"default");
513 const std::string& format =
"default");
517 const std::string& format =
"default");
521 const std::string& format =
"default");
524 std::ostream&
print(
const label& l, std::ostream& o,
525 const std::string& format =
"default");
529 const std::string& format =
"default");
532 std::ostream&
print(
const weight& w, std::ostream& o,
533 const std::string& format =
"default");
536 void set_format(std::ostream& o,
const std::string& format);
561 bool prune =
true,
const std::string& algo =
"auto");
590 unsigned num_initial = 1,
591 unsigned num_final = 1,
592 float loop_chance = 0.0);
601 unsigned num_states);
612 const std::string& format =
"default",
623 const std::string& format =
"default");
631 const std::string& format =
"default");
671 boost::optional<unsigned> num = {},
672 boost::optional<unsigned> len = {});
742 const std::string& algo =
"greedy");
762 const std::string& algo =
"auto");
776 const std::string& algo =
"auto");
automaton complete(const automaton &aut)
A completed copy of aut.
polynomial lightest(const automaton &aut, boost::optional< unsigned > num={})
The approximated behavior of an automaton with smallest weights.
bool is_realtime(const automaton &aut)
Whether has no spontaneous transition, and is letterized.
bool is_valid(const automaton &e)
Whether automaton is valid (epsilon-cycles converge).
bool are_equivalent(const automaton &lhs, const automaton &rhs)
Whether compute the same series.
expression expression_one(const context &c, rat::identities ids)
The expression for \e.
automaton random_automaton_deterministic(const context &ctx, unsigned num_states)
Produce a random deterministic automaton.
automaton coaccessible(const automaton &aut)
The coaccessible subautomaton of aut.
expression expand(const expression &e)
Distribute product over addition recursively under the starred subexpressions and group the equal mon...
automaton project(const automaton &aut, unsigned tape)
Keep a single tape from a multiple-tape automaton.
bool has_bounded_lag(const automaton &aut)
Whether the transducer has bounded lag.
context context_of(const automaton &a)
The context of this automaton.
bool is_codeterministic(const automaton &aut)
Whether aut is codeterministic.
automaton component(const automaton &aut, unsigned num)
The automaton of a strongly connected component.
std::shared_ptr< const detail::label_base > label
automaton condense(const automaton &aut)
The condensation of aut such that each state is a strongly connected component.
weightset_mixin< detail::r_impl > r
automaton strip(const automaton &a)
The automaton in a with its metadata layers removed.
bool are_isomorphic(const automaton &lhs, const automaton &rhs)
Whether there exists an isomorphism between the states of lhs and those of rhs.
bool is_out_sorted(const automaton &aut)
Whether the outgoing transitions of each state have increasing labels.
automaton standard(const automaton &a)
A standardized a.
polynomial ldiv(const polynomial &lhs, const polynomial &rhs)
Left-division of two polynomials (lhs \ rhs).
std::shared_ptr< const detail::context_base > context
A dyn::context.
automaton codeterminize(const automaton &aut, const std::string &algo="auto")
The codeterminized automaton.
polynomial shortest(const automaton &aut, boost::optional< unsigned > num={}, boost::optional< unsigned > len={})
The approximated behavior of an automaton.
automaton universal(const automaton &aut)
The universal automaton of aut.
expression read_expression(const context &ctx, rat::identities ids, std::istream &is, const std::string &format="default")
Read an expression from a stream.
automaton trim(const automaton &aut)
The trim subautomaton of aut.
bool is_partial_identity(const automaton &aut)
Whether aut realizes a partial identity.
polynomial derivation(const expression &exp, const label &lbl, bool breaking=false)
Derive exp with respect to s.
bool is_trim(const automaton &aut)
Whether has no useless state.
automaton 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.
automaton divkbaseb(const context &ctx, unsigned divisor, unsigned base)
An automaton which accepts a word n representing a number in base b iff k|n.
std::string type(const automaton &a)
The implementation type of a.
bool is_standard(const automaton &aut)
Whether is standard (unique initial state, with weight one, no incoming transition).
automaton partial_identity(const automaton &aut)
Create a partial identity transducer from aut.
expression expression_zero(const context &c, rat::identities ids)
The expression for \z.
bool is_complete(const automaton &aut)
Whether aut is complete.
std::ostream & print(const automaton &aut, std::ostream &out, const std::string &format="default")
Print automaton a on o using format format.
std::istringstream is
The input stream: the specification to translate.
automaton cotrie(const polynomial &p)
A reversed trie-like automaton (multiple initial states, single final state) automaton to accept p...
automaton de_bruijn(const context &ctx, unsigned n)
A simple NFA for (a+b)*a(a+b)^n.
automaton_editor * make_automaton_editor(const context &ctx)
Build an automatonset from its context.
expression transposition(const expression &r)
Add the transposition operator to r.
bool is_useless(const automaton &aut)
Whether has no useful state.
automaton synchronize(const automaton &aut)
Create a synchronized transducer from aut.
std::set< std::pair< std::string, std::string >> letter_class_t
A set of letter ranges.
automaton reduce(const automaton &aut)
Reduce aut.
expression star_normal_form(const expression &e)
A normalized form where star is applied only to proper expressions.
automaton determinize(const automaton &aut, const std::string &algo="auto")
The determinized automaton.
bool is_normalized(const automaton &aut)
Whether is normalized (in the Thompson sense), i.e., standard and co-standard.
std::ostream & info(const automaton &aut, std::ostream &out, bool detailed=false)
Output various facts about an automaton.
automaton compose(automaton &lhs, automaton &rhs)
The composition of transducers lhs and rhs.
weight read_weight(const context &ctx, std::istream &is)
Read a weight from a stream.
automaton sort(const automaton &a)
A copy of a with normalized state numbers.
automaton filter(const automaton &aut, const std::vector< unsigned > &ss)
The subautomaton based on aut, with only states in ss visible.
label synchronizing_word(const automaton &aut, const std::string &algo="greedy")
A synchronizing word, or raise if there is none.
automaton left_mult(const weight &w, const automaton &aut)
The left-multiplication of an automaton with w as weight.
bool is_synchronizing(const automaton &aut)
Whether is synchronizing.
automaton conjunction(const automaton &lhs, const automaton &rhs, bool lazy=false)
The conjunction (aka synchronized product) of automata.
bool is_empty(const automaton &aut)
Whether has no state.
automaton normalize(const automaton &aut)
Normalize automaton aut.
automaton union_a(const automaton &lhs, const automaton &rhs)
Union of two automata (plain graph union).
automaton derived_term(const expression &exp, const std::string &algo="auto")
The derived-term automaton of exp.
automaton prefix(const automaton &aut)
Create a prefix automaton from aut.
automaton letterize(const automaton &aut)
The automaton with letter transitions instead of words.
automaton complement(const automaton &aut)
The complement of aut.
automaton factor(const automaton &aut)
Create a factor automaton from aut.
automaton subword(const automaton &aut)
Create a subword automaton from aut.
bool is_deterministic(const automaton &aut)
Whether aut is deterministic.
automaton push_weights(const automaton &aut)
The weight pushing automaton of aut.
std::ostream & operator<<(std::ostream &o, type_t t)
std::size_t num_components(const automaton &aut)
The number of strongly connected components.
static dyn::context ctx(const driver &d)
Get the context of the driver.
std::shared_ptr< const detail::weight_base > weight
bool is_cycle_ambiguous(const automaton &aut)
Whether the automaton is cycle-ambiguous.
automaton difference(const automaton &lhs, const automaton &rhs)
An automaton whose behavior is that of lhs on words not accepted by rhs.
automaton shuffle(const automaton &lhs, const automaton &rhs)
The shuffle product of automata lhs and rhs.
bool has_twins_property(const automaton &aut)
Whether the automaton has the twins property.
automaton costandard(const automaton &a)
A standardized transpositive a.
automaton cerny(const context &ctx, unsigned num_states)
Produce a Černý automaton of num_states states.
std::shared_ptr< detail::automaton_base > automaton
std::shared_ptr< const detail::expansion_base > expansion
automaton delay_automaton(const automaton &a)
The automaton with the delay of each state.
context join(const context &lhs, const context &rhs)
The join between two contexts, i.e., their lowest common supertype.
automaton 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.
expression to_expression(const automaton &aut, rat::identities ids={}, const std::string &algo="auto")
An expression denoting the language of aut.
polynomial split(const expression &exp)
Break exp.
static identities ids(const driver &d)
Get the identities of the driver.
expression rdiv(const expression &lhs, const expression &rhs)
Right-division of two expressions (lhs \ rhs).
bool is_ambiguous(const automaton &aut)
Whether aut is ambiguous.
automaton ladybird(const context &ctx, unsigned n)
The ladybird automaton with n states.
automaton sum(const automaton &lhs, const automaton &rhs)
Sum of two standard automata.
weight constant_term(const expression &e)
The weight associated to the empty word in e.
automaton thompson(const expression &e)
The Thompson automaton of e.
bool is_costandard(const automaton &aut)
Whether is costandard (unique final state, with weight one, no outcoming transition).
automaton suffix(const automaton &aut)
Create a suffix automaton from aut.
automaton focus(const automaton &aut, unsigned tape)
Focus on a specific tape of a tupleset automaton.
automaton to_automaton(const expression &exp, const std::string &algo="auto")
An automaton denoting the language of exp.
label read_label(const context &ctx, std::istream &is, const std::string &format="default")
Read a label from a stream.
automaton copy(const automaton &aut)
A copy of aut.
context make_context(const std::string &name)
Build a context from its name.
automaton levenshtein(const context &ls)
The transducer representing the Levenshtein distance.
automaton multiply(const automaton &lhs, const automaton &rhs)
Multiply (concatenate) two standard automata.
std::string get_format(std::ostream &o)
Get the output format for o.
automaton zpc(const expression &exp, const std::string &algo="auto")
The ZPC automaton of exp.
automaton insplit(const automaton &aut)
Split automaton on the incoming transition.
std::shared_ptr< const detail::polynomial_base > polynomial
automaton eliminate_state(const automaton &aut, int s=-1)
The LAO automaton aut with state s removed.
automaton u(const context &ctx, unsigned n)
The Brzozowski universal witness.
bool is_eps_acyclic(const automaton &aut)
Whether has no cycle of spontaneous transitions.
expression concatenate(const expression &lhs, const expression &rhs)
Concatenate two expressions.
bool is_coaccessible(const automaton &aut)
Whether aut is coaccessible.
weight eval(const automaton &aut, const label &l)
Evaluate l on aut.
polynomial lgcd(const polynomial &lhs, const polynomial &rhs)
Left greatest common divisor of two polynomials (lhs \ rhs).
bool is_letterized(const automaton &aut)
Whether aut is letterized.
automaton realtime(const automaton &aut)
Create the realtime automaton (letterized and proper).
bool is_proper(const automaton &aut)
Whether has no spontaneous transition.
automaton proper(const automaton &aut, direction dir=direction::backward, bool prune=true, const std::string &algo="auto")
An equivalent automaton without spontaneous transitions.
bool is_functional(const automaton &aut)
Whether aut is functional.
automaton 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.
std::shared_ptr< detail::expression_base > expression
automaton read_automaton(std::istream &is, const std::string &format="default", bool strip=true)
Read an automaton from a stream.
automaton cominimize(const automaton &aut, const std::string &algo="auto")
The cominimized automaton.
weight weight_series(const automaton &aut)
Compute weight of the series.
bool less_than(const expression &lhs, const expression &rhs)
Ordering between expressions.
unsigned star_height(const expression &rs)
Star height of an expression.
automaton accessible(const automaton &aut)
The accessible subautomaton of aut.
expansion to_expansion(const expression &exp)
First order development of a exp.
label ambiguous_word(const automaton &aut)
An ambiguous word, or raise if there is none.
automaton right_mult(const automaton &aut, const weight &w)
The right-mult automaton with w as weight.
bool is_synchronized_by(const automaton &aut, const label &word)
Whether the word synchronizes aut.
automaton transpose(automaton &aut)
Transpose aut.
bool is_accessible(const automaton &aut)
Whether aut is accessible.
rat::identities identities(const expression &exp)
The identities of expression exp.
automaton infiltration(const automaton &lhs, const automaton &rhs)
The infiltration of automata lhs and rhs.
automaton star(const automaton &aut)
Star of a standard automaton.
automaton pair(const automaton &aut, bool keep_initials=false)
Build the pair automaton of the given automaton.
automaton 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...
automaton trie(const polynomial &p)
A trie-like automaton (single initial state, multiple final states) to accept p.
context make_word_context(const context &ctx)
The context for words.
std::size_t num_tapes(const context &ctx)
The number of input tapes.
bool is_synchronized(const automaton &aut)
Whether is synchronized.
automaton minimize(const automaton &aut, const std::string &algo="auto")
The minimized automaton.
expression tuple(const expression &lhs, const expression &rhs)
Build a two-tape expression from two expressions.
polynomial read_polynomial(const context &ctx, std::istream &is)
Read a polynomial from a stream.
void set_format(std::ostream &o, const std::string &format)
Specify the output format for o.