algos.hh

Go to the documentation of this file.

#pragma once

#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> // LIBVCSN_API

namespace vcsn
{
  namespace dyn LIBVCSN_API
  {
    automaton accessible(const automaton& aut);

    word ambiguous_word(const automaton& aut);

    bool are_equivalent(const automaton& lhs, const automaton& rhs);

    bool are_equivalent(const expression& lhs, const expression& rhs);

    bool are_isomorphic(const automaton& lhs, const automaton& rhs);

    automaton cerny(const context& ctx, unsigned num_states);

    automaton coaccessible(const automaton& aut);

    automaton codeterminize(const automaton& aut,
                            const std::string& algo = "auto");

    automaton cominimize(const automaton& aut,
                         const std::string& algo = "auto");

    automaton complement(const automaton& aut);

    expansion complement(const expansion& x);

    expression complement(const expression& r);

    automaton complete(const automaton& aut);

    automaton component(const automaton& aut, unsigned num);

    automaton compose(const automaton& lhs, const automaton& rhs,
                      bool lazy = false);

    expansion compose(const expansion& lhs, const expansion& rhs);

    expression compose(const expression& lhs, const expression& rhs);

    polynomial compose(const polynomial& lhs, const polynomial& rhs);

    expression concatenate(const expression& lhs, const expression& rhs);

    automaton condense(const automaton& aut);

    automaton conjunction(const automaton& lhs, const automaton& rhs,
                          bool lazy = false);

    automaton conjunction(const std::vector<automaton>& as,
                          bool lazy = false);

    automaton conjunction(const automaton& aut, unsigned n);

    expansion conjunction(const expansion& lhs, const expansion& rhs);

    expression conjunction(const expression& lhs, const expression& rhs);

    polynomial conjunction(const polynomial& lhs, const polynomial& rhs);

    automaton conjugate(const automaton& aut);

    weight constant_term(const expression& e);

    context context_of(const automaton& a);

    context context_of(const expansion& r);

    context context_of(const expression& r);

    context context_of(const polynomial& r);

    automaton copy(const automaton& aut);

    automaton copy(const automaton& aut, const context& ctx);

    expression copy(const expression& exp,
                    const context& ctx, identities ids);

    automaton costandard(const automaton& a);

    automaton cotrie(const polynomial& p);

    automaton cotrie(const context& ctx, std::istream& is,
                     const std::string& format = "default");

    automaton de_bruijn(const context& ctx, unsigned n);

    automaton delay_automaton(const automaton& a);

    polynomial derivation(const expression& exp, const label& lbl,
                          bool breaking = false);

    automaton derived_term(const expression& exp,
                           const std::string& algo = "auto");

    automaton determinize(const automaton& aut,
                          const std::string& algo = "auto");

    automaton difference(const automaton& lhs, const automaton& rhs);

    expression difference(const expression& lhs, const expression& rhs);

    automaton divkbaseb(const context& ctx, unsigned divisor, unsigned base);

    automaton double_ring(const context& ctx, unsigned n,
                          const std::vector<unsigned>& f);

    automaton eliminate_state(const automaton& aut,
                              int s = -1);

    weight evaluate(const automaton& aut, const word& l);

    weight evaluate(const automaton& aut, const polynomial& p);

    expression expand(const expression& e);

    expression expression_one(const context& c, identities ids);

    expression expression_zero(const context& c, identities ids);

    automaton factor(const automaton& aut);

    automaton filter(const automaton& aut, const std::vector<unsigned>& ss);

    automaton focus(const automaton& aut, unsigned tape);

    bool has_twins_property(const automaton& aut);

    bool has_lightening_cycle(const automaton& aut);

    bool has_bounded_lag(const automaton& aut);

    identities identities_of(const expression& exp);

    automaton inductive(const expression& e, const std::string& algo = "auto");

    automaton infiltrate(const automaton& lhs, const automaton& rhs);

    automaton infiltrate(const std::vector<automaton>& as);

    expression infiltrate(const expression& lhs, const expression& rhs);

    std::ostream& info(const automaton& aut, std::ostream& out = std::cout,
                       unsigned details = 2);

    std::ostream& info(const expression& exp, std::ostream& out = std::cout);

    automaton insplit(const automaton& aut, bool lazy = false);

    bool is_accessible(const automaton& aut);

    bool is_ambiguous(const automaton& aut);

    bool is_coaccessible(const automaton& aut);

    bool is_codeterministic(const automaton& aut);

    bool is_complete(const automaton& aut);

    bool is_costandard(const automaton& aut);

    bool is_cycle_ambiguous(const automaton& aut);

    bool is_deterministic(const automaton& aut);

    bool is_empty(const automaton& aut);

    bool is_eps_acyclic(const automaton& aut);

    bool is_functional(const automaton& aut);

    bool is_letterized(const automaton& aut);

    bool is_partial_identity(const automaton& aut);

    bool is_normalized(const automaton& aut);

    bool is_out_sorted(const automaton& aut);

    bool is_proper(const automaton& aut);

    bool is_realtime(const automaton& aut);

    bool is_standard(const automaton& aut);

    bool is_synchronized(const automaton& aut);

    bool is_synchronized_by(const automaton& aut, const word& word);

    bool is_synchronizing(const automaton& aut);

    bool is_trim(const automaton& aut);

    bool is_useless(const automaton& aut);

    bool is_valid(const automaton& e);

    bool is_valid(const expression& e);

    context join(const context& lhs, const context& rhs);

    automaton ladybird(const context& ctx, unsigned n);

    automaton ldivide(const automaton& lhs, const automaton& rhs);

    expansion ldivide(const expansion& lhs, const expansion& rhs);

    expression ldivide(const expression& lhs, const expression& rhs);

    label ldivide(const label& lhs, const label& rhs);

    polynomial ldivide(const polynomial& lhs, const polynomial& rhs);

    weight ldivide(const weight& lhs, const weight& rhs);

    polynomial lgcd(const polynomial& lhs, const polynomial& rhs);

    automaton lweight(const weight& w, const automaton& aut,
                        const std::string& algo = "auto");

    expansion lweight(const weight& w, const expansion& exp);

    expression lweight(const weight& w, const expression& exp);

    polynomial lweight(const weight& w, const polynomial& p);

    bool less_than(const expression& lhs, const expression& rhs);

    automaton letterize(const automaton& aut);

    automaton levenshtein(const context& ls);

    automaton lift(const automaton& aut,
                   const std::vector<unsigned>& tapes = {},
                   identities ids = {});

    expression lift(const expression& e);

    polynomial lightest(const automaton& aut, unsigned num = 1,
                        const std::string& algo = "auto");

    automaton lightest_automaton(const automaton& aut,
                                 unsigned num = 1,
                                 const std::string& algo = "auto");

    context make_context(const std::string& name);

    automaton_editor* make_automaton_editor(const context& ctx);

    context make_word_context(const context& ctx);

    automaton multiply(const automaton& lhs, const automaton& rhs,
                       const std::string& algo = "auto");

    automaton multiply(const automaton& aut, int min, int max = -2,
                       const std::string& algo = "auto");

    expression multiply(const expression& lhs, const expression& rhs);

    expression multiply(const expression& e, int min, int max = -2);

    label multiply(const label& lhs, const label& rhs);

    label multiply(const label& l, int num);

    polynomial multiply(const polynomial& lhs, const polynomial& rhs);

    weight multiply(const weight& lhs, const weight& rhs);

    weight multiply(const weight& e, int min, int max = -2);

    automaton minimize(const automaton& aut,
                       const std::string& algo = "auto");

    automaton normalize(const automaton& aut);

    std::size_t num_components(const automaton& aut);

    std::size_t num_tapes(const context& ctx);

    automaton pair(const automaton& aut, bool keep_initials = false);

    automaton partial_identity(const automaton& aut);

    expression partial_identity(const expression& e);

    automaton prefix(const automaton& aut);

    std::ostream& print(const automaton& aut, std::ostream& out = std::cout,
                        const std::string& format = "default");

    std::ostream& print(const context& c, std::ostream& out = std::cout,
                        const std::string& format = "default");

    std::ostream& print(const expansion& e, std::ostream& out = std::cout,
                        const std::string& format = "default");

    std::ostream& print(const expression& e, std::ostream& out = std::cout,
                        const std::string& format = "default");

    std::ostream& print(const label& l, std::ostream& out = std::cout,
                        const std::string& format = "default");

    std::ostream& print(const polynomial& p, std::ostream& out = std::cout,
                        const std::string& format = "default");

    std::ostream& print(const weight& w, std::ostream& out = std::cout,
                        const std::string& format = "default");

    automaton quotkbaseb(const context& ctx, unsigned divisor, unsigned base);

    void set_format(std::ostream& out, const std::string& format);

    std::string get_format(std::ostream& out);

    automaton project(const automaton& aut, unsigned tape);

    context project(const context& ctx, unsigned tape);

    expansion project(const expansion& xpn, unsigned tape);

    expression project(const expression& exp, unsigned tape);

    polynomial project(const polynomial& p, unsigned tape);

    label project(const label& p, unsigned tape);

    automaton proper(const automaton& aut,
                     direction dir = direction::backward,
                     bool prune = true, const std::string& algo = "auto");

    automaton push_weights(const automaton& aut);

    automaton 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 = "");

    automaton random_automaton_deterministic(const context& ctx,
                                             unsigned num_states);

    expression
    random_expression(const context& ctx,
                      const std::string& param = "+, ., *=.2, w., .w, length=10",
                      identities ids = {});

    weight random_weight(const context& ctx, const std::string& param);

    automaton rdivide(const automaton& lhs, const automaton& rhs);

    expression rdivide(const expression& lhs, const expression& rhs);

    label rdivide(const label& lhs, const label& rhs);

    weight rdivide(const weight& lhs, const weight& rhs);

    automaton read_automaton(std::istream& is,
                             const std::string& format = "default",
                             bool strip = true);

    expression read_expression(const context& ctx, identities ids,
                               std::istream& is,
                               const std::string& format = "default");

    label read_label(const context& ctx, std::istream& is,
                     const std::string& format = "default");

    polynomial read_polynomial(const context& ctx, std::istream& is);

    weight read_weight(const context& ctx, std::istream& is);

    automaton realtime(const automaton& aut);

    automaton reduce(const automaton& aut);

    automaton rweight(const automaton& aut, const weight& w,
                         const std::string& algo = "auto");

    expansion rweight(const expansion& aut, const weight& w);

    expression rweight(const expression& exp, const weight& w);

    polynomial rweight(const polynomial& p, const weight& w);

    automaton scc(const automaton& aut, const std::string& algo = "auto");

    polynomial shortest(const automaton& aut,
                        boost::optional<unsigned> num = {},
                        boost::optional<unsigned> len = {});

    automaton shuffle(const automaton& lhs, const automaton& rhs);

    automaton shuffle(const std::vector<automaton>& as);

    expression shuffle(const expression& lhs, const expression& rhs);

    automaton sort(const automaton& a);

    polynomial split(const expression& exp);

    polynomial split(const polynomial& p);

    automaton standard(const automaton& a);

    automaton standard(const expression& e);

    automaton star(const automaton& aut, const std::string& algo = "auto");

    unsigned star_height(const expression& rs);

    expression star_normal_form(const expression& e);

    automaton strip(const automaton& a);

    automaton suffix(const automaton& aut);

    automaton subword(const automaton& aut);

    automaton add(const automaton& lhs, const automaton& rhs,
                  const std::string& algo = "auto");

    expression add(const expression& lhs, const expression& rhs);

    expansion add(const expansion& lhs, const expansion& rhs);

    polynomial add(const polynomial& lhs, const polynomial& rhs);

    weight add(const weight& lhs, const weight& rhs);

    automaton synchronize(const automaton& aut);

    word synchronizing_word(const automaton& aut,
                            const std::string& algo = "greedy");

    automaton thompson(const expression& e);

    automaton to_automaton(const expression& exp,
                           const std::string& algo = "auto");

    expansion to_expansion(const expression& exp);

    expression to_expression(const automaton& aut,
                             identities ids = {},
                             const std::string& algo = "auto");

    expression to_expression(const context& ctx, identities ids,
                             const label& l);

    expression to_expression(const context& ctx, identities ids,
                             const letter_class_t& letters,
                             bool accept = true);

    automaton transpose(automaton& aut);

    expression transpose(const expression& e);

    expression transposition(const expression& r);

    automaton trie(const polynomial& p);

    automaton trie(const context& ctx, std::istream& is,
                   const std::string& format = "default");

    automaton trim(const automaton& aut);

    automaton tuple(const automaton& lhs, const automaton& rhs);

    automaton tuple(const std::vector<automaton>& as);

    context tuple(const context& lhs, const context& rhs);

    context tuple(const std::vector<context>& ctxs);

    expansion tuple(const std::vector<expansion>& rs);

    expression tuple(const expression& lhs, const expression& rhs);

    expression tuple(const std::vector<expression>& rs);

    polynomial tuple(const std::vector<polynomial>& ps);

    std::string type(const automaton& a);

    automaton u(const context& ctx, unsigned n);

    automaton universal(const automaton& aut);

    weight weight_one(const context& c);

    weight weight_series(const automaton& aut);

    weight weight_zero(const context& c);

    automaton zpc(const expression& exp, const std::string& algo = "auto");

    std::ostream& operator<<(std::ostream& o, const automaton& a);

    std::ostream& operator<<(std::ostream& o, const context& c);

    std::ostream& operator<<(std::ostream& o, const expansion& e);

    std::ostream& operator<<(std::ostream& o, const expression& r);

    std::ostream& operator<<(std::ostream& o, const label& l);

    std::ostream& operator<<(std::ostream& o, const polynomial& p);

    std::ostream& operator<<(std::ostream& o, const weight& w);
  }
}