43 "derived-term algorithm",
47 {
"breaking_derivation",
"derivation,breaking"},
48 {
"breaking_expansion",
"expansion,breaking"},
50 {
"derivation,breaking", dta{
derivation,
true,
false}},
51 {
"derivation,deterministic",dta{
derivation,
false,
true}},
52 {
"derivation_breaking",
"derivation,breaking"},
53 {
"expansion", dta{
expansion,
false,
false}},
54 {
"expansion,breaking", dta{
expansion,
true,
false}},
55 {
"expansion,deterministic", dta{
expansion,
false,
true}},
56 {
"expansion_breaking",
"expansion,breaking"},
59 if (boost::starts_with(algo,
"lazy,"))
60 algo = algo.substr(5);
79 template <
typename ExpSet,
84 :
gens{rs.labelset()->generators()}
93 template <
typename ExpSet>
128 template <
typename ExpSet>
130 :
public automaton_decorator<expression_automaton<mutable_automaton<context_t_of<ExpSet>>>>
151 static auto res =
symbol{
"derived_term_automaton<"
159 o <<
"derived_term_automaton<";
160 return rs_.print_set(o, fmt) <<
'>';
165 :
super_t{make_shared_ptr<automaton_t>(
rs)}
184 while (!
aut_->todo_.empty())
186 auto p = std::move(
aut_->todo_.top());
197 while (!
aut_->todo_.empty())
199 auto p = std::move(
aut_->todo_.top());
214 for (
const auto& p:
split(
rs_, expression))
217 aut_->set_initial(expression,
ws_.one());
223 const auto& orig =
aut_->origins();
224 auto sn = orig.at(s);
239 typename = std::enable_if<labelset_t_of<ES>::is_free()>>
242 aut_->set_lazy(s,
false);
249 auto m =
ps_.determinize(p);
253 for (
const auto& m: p)
261 aut_->set_lazy(s,
false);
267 for (
const auto& p:
expansion.polynomials)
269 for (
const auto& m1: p.second)
275 auto m =
ps_.determinize(p.second);
279 for (
const auto& m: p.second)
305 template <
typename ExpSet>
307 = std::shared_ptr<detail::derived_term_automaton_impl<ExpSet>>;
309 template <
typename ExpSet>
316 return make_shared_ptr<res_t>(
rs, algo);
324 template <
typename ExpSet>
325 std::enable_if_t<labelset_t_of<ExpSet>::is_free(),
326 expression_automaton<mutable_automaton<typename ExpSet::context_t>>>
328 const typename ExpSet::value_t&
r,
329 const std::string& algo =
"auto")
333 return dt->operator()(
r);
341 template <
typename ExpSet>
342 std::enable_if_t<!labelset_t_of<ExpSet>::is_free(),
343 expression_automaton<mutable_automaton<typename ExpSet::context_t>>>
345 const typename ExpSet::value_t&
r,
346 const std::string& algo =
"auto")
350 "derived_term: cannot use derivation on non-free labelsets");
355 return dt->via_expansion(r);
363 template <
typename ExpSet,
typename String>
366 const auto& e = exp->as<ExpSet>();
367 const auto& rs = e.expressionset();
368 const auto&
r = e.expression();
369 if (boost::starts_with(algo,
"lazy"))
373 "derived_term: laziness works only with expansions");
typename expressionset_t::value_t expression_t
Our state names: expressions.
std::ostream & print_set(std::ostream &o, format fmt={}) const
to_expansion_t to_expansion_
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Specify a variety of derived-term construction.
bool determinize
Whether to determinize the expansions and produce a deterministic automaton, at the expense of possib...
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
derived_term_algo(std::string algo)
From algo name to algo.
auto weight_of(Args &&...args) const -> decltype(aut_-> weight_of(std::forward< Args >(args)...))
std::shared_ptr< detail::expression_automaton_impl< Aut >> expression_automaton
An expression automaton as a shared pointer.
automaton_t operator()(const expression_t &expression)
Compute the derived-term automaton.
automaton_t via_derivation(const expression_t &expression)
Compute the derived-term automaton via derivation.
state_t_of< automaton_t > state_t
expressionset_t rs_
The expression's set.
auto make_derived_term_automaton(const ExpSet &rs, const detail::derived_term_algo &algo) -> derived_term_automaton< ExpSet >
void complete_via_derivation_(state_t s, const expression_t &src)
Compute the outgoing transitions of src.
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
std::enable_if_t< labelset_t_of< ExpSet >::is_free(), expression_automaton< mutable_automaton< typename ExpSet::context_t > > > derived_term(const ExpSet &rs, const typename ExpSet::value_t &r, const std::string &algo="auto")
The derived-term automaton, for free labelsets.
context_t_of< expressionset_t > context_t
std::shared_ptr< const detail::expansion_base > expansion
automaton_t aut_
The wrapped automaton, possibly const.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
weightset_mixin< detail::r_impl > r
An input/output format for valuesets.
value_t determinize(const value_t &v) const
Turn the polynomials into (normalized) monomials.
Additional members when the labelset is free.
Provide a variadic mul on top of a binary mul(), and one().
weight_t_of< ExpSet > constant_term(const ExpSet &rs, const typename ExpSet::value_t &e)
The constant term of e.
expression_automaton< mutable_automaton< context_t >> automaton_t
The type of the (strict) automaton we build.
weightset_t_of< context_t > weightset_t
derived_term_automaton_members< expressionset_t > members_
Possibly the generators.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
derived_term_automaton_members(const ExpSet &rs)
void complete_via_expansion_(state_t s, const expression_t &src)
Compute the outgoing transitions of src.
A mapping from strings to Values.
std::shared_ptr< detail::derived_term_automaton_impl< ExpSet >> derived_term_automaton
A derived-term automaton as a shared pointer.
auto is_lazy(Args &&...args) const -> decltype(aut_-> is_lazy(std::forward< Args >(args)...))
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Aggregate an automaton, and forward calls to it.
std::shared_ptr< detail::automaton_base > automaton
void init_(const expression_t &expression)
Initialize the computation: build the initial states.
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
std::shared_ptr< const node< Context >> expression
Compute the derived-term automaton from an expression.
auto all_out(state_t s) const -> decltype(vcsn::detail::all_out(aut_, s))
All the outgoing transitions.
weightset_t ws_
Its weightset.
derived_term_automaton_impl(const expressionset_t &rs, derived_term_algo algo)
algo_t algo
Core algorithm.
derived_term_automaton_members(const ExpSet &)
derived_term_algo(algo_t a, bool b, bool d)
std::shared_ptr< detail::expression_base > expression
rat::expression_polynomial_t< ExpSet > derivation(const ExpSet &rs, const typename ExpSet::value_t &e, label_t_of< ExpSet > a, bool breaking=false)
Derive an expression wrt to a letter.
expression_polynomialset_t< ExpSet > make_expression_polynomialset(const ExpSet &rs)
From a ExpSet to its polynomialset.
bool breaking
Whether to break sums.
void complete_(state_t s) const
Complete a state: find its outgoing transitions.
derived_term_algo algo_
How derived terms are computed.
typename labelset_t_of< ExpSet >::genset_t genset_t
The alphabet.
automaton_t via_expansion(const expression_t &expression)
Compute the derived-term automaton via expansion.
auto label_of(Args &&...args) const -> decltype(aut_-> label_of(std::forward< Args >(args)...))
rat::expression_polynomial_t< ExpSet > split(const ExpSet &rs, const typename ExpSet::value_t &e)
Split an expression.