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/core/rat/identities.hh>
#include <vcsn/ctx/fwd.hh>
#include <vcsn/dyn/fwd.hh>
#include <vcsn/misc/direction.hh>
#include <vcsn/misc/export.hh>

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

    label 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(automaton& lhs, automaton& rhs, bool lazy = false);

    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);

    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);

    automaton copy(const automaton& aut);

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

    expression copy(const expression& exp,
                    const context& ctx, rat::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 eval(const automaton& aut, const label& l);

    expression expand(const expression& e);

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

    expression expression_zero(const context& c, rat::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);

    rat::identities identities(const expression& exp);

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

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

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

    std::ostream& info(const automaton& aut, std::ostream& out,
                       bool detailed = false);

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

    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 label& 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);

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

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

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

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

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

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

    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 = {},
                   rat::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,
                                 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,
                       const std::string& algo = "auto");

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

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

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

    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);

    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);

    automaton prefix(const automaton& aut);

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

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

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

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

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

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

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

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

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

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

    context project(const context& ctx, 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,
                               float loop_chance = 0.0);

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

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

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

    expression read_expression(const context& ctx, rat::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 right_mult(const automaton& aut, const weight& w,
                         const std::string& algo = "auto");

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

    expression right_mult(const expression& aut, 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 sum(const automaton& lhs, const automaton& rhs,
                  const std::string& algo = "auto");

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

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

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

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

    automaton synchronize(const automaton& aut);

    label 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,
                             rat::identities ids = {},
                             const std::string& algo = "auto");

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

    expression to_expression(const context& ctx, rat::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);

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

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

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

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

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

    automaton universal(const automaton& aut);

    weight weight_series(const automaton& aut);

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

// dyn::automaton and the like are actually type aliases for
// std::shared_ptr, so for ADL to work properly, we need these
// operators to be defined in std.
namespace std LIBVCSN_API
{
  std::ostream& operator<<(std::ostream& o, const vcsn::dyn::automaton& a);

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

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

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

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

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

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