Vcsn  2.3
Be Rational
to-expression.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <boost/heap/fibonacci_heap.hpp>
4 
5 #include <vcsn/algos/copy.hh>
6 #include <vcsn/algos/lift.hh>
7 #include <vcsn/core/automaton.hh> // all_in
9 #include <vcsn/core/rat/info.hh>
10 #include <vcsn/core/rat/size.hh>
11 #include <vcsn/dyn/value.hh>
12 #include <vcsn/misc/builtins.hh>
13 #include <vcsn/misc/getargs.hh>
14 #include <vcsn/misc/vector.hh>
15 
16 namespace vcsn
17 {
18  namespace detail
19  {
20  /*----------------.
21  | Naive profiler. |
22  `----------------*/
23 
26  template <Automaton Aut>
28  {
29  using automaton_t = Aut;
32 
34  : aut_(aut)
35  {}
36 
41  {
43  : state_(state)
44  {}
45 
46  bool operator<(const state_profile& rhs) const
47  {
48  return std::make_tuple(rhs.size_, rhs.has_loop_, rhs.state_)
49  < std::make_tuple(size_, has_loop_, state_);
50  }
51 
52  friend std::ostream& operator<<(std::ostream& o, const state_profile& p)
53  {
54  return o << p.state_
55  << 's' << p.size_
56  << 'l' << p.has_loop_;
57  }
58 
61  size_t size_;
62  bool has_loop_ = false;
64  };
65 
68  {
69  auto p = state_profile{state};
70  update(p);
71  return p;
72  }
73 
75  {}
76 
78  {
79  size_t out = 0;
80  for (auto t: all_out(aut_, p.state_))
81  if (aut_->dst_of(t) == p.state_)
82  p.has_loop_ = true;
83  else
84  ++out;
85  size_t in = all_in(aut_, p.state_).size();
86  p.size_ = in * out;
87  }
88 
90  };
91 
92  /*-------------------.
93  | Delgado profiler. |
94  `-------------------*/
95 
98  template <Automaton Aut>
100  {
101  using automaton_t = Aut;
104 
110  delgado_profiler(const automaton_t& aut, bool count_labels = false)
111  : aut_{aut}
112  , count_labels_{count_labels}
114  {}
115 
117  {
119  : state_(state)
120  {}
121 
122  bool operator<(const state_profile& rhs) const
123  {
124  return std::make_tuple(rhs.size_, rhs.state_)
125  < std::make_tuple(size_, state_);
126  }
127 
128  friend std::ostream& operator<<(std::ostream& o, const state_profile& p)
129  {
130  return o << p.state_
131  << 's' << p.size_;
132  }
133 
134  size_t size_;
136  };
137 
140  {
141  auto p = state_profile{state};
142  update(p);
143  return p;
144  }
145 
150  {
151  auto& res = transition_cache_[t];
152  if (res == 0)
153  {
154  using expset_t = weightset_t_of<automaton_t>;
155  if (count_labels_)
156  res = rat::make_info<expset_t>(aut_->weight_of(t)).atom;
157  else
158  res = rat::size<expset_t>(aut_->weight_of(t));
159  }
160  return res;
161  }
162 
168  {
169  if (transition_cache_.size() <= t)
170  transition_cache_.resize(t + 1, 0);
171  transition_cache_[t] = 0;
172  }
173 
179  {
180  // The cumulated size of the incoming transitions excluding loops.
181  size_t size_in = 0;
182  // The number of incoming transitions excluding loops.
183  size_t ins = 0;
184  // The size of the loop, if there is one.
185  size_t size_loop = 0;
186  for (auto t: all_in(aut_, p.state_))
187  if (aut_->src_of(t) == p.state_)
188  size_loop += size_of_transition(t);
189  else
190  {
191  ++ins;
192  size_in += size_of_transition(t);
193  }
194 
195  // The cumulated size of the outgoing transitions excluding loops.
196  size_t size_out = 0;
197  // The number of outgoing transitions excluding loops.
198  size_t outs = 0;
199  for (auto t: all_out(aut_, p.state_))
200  if (aut_->dst_of(t) != p.state_)
201  {
202  ++outs;
203  size_out += size_of_transition(t);
204  }
205 
206  p.size_ = (size_in * (outs - 1)
207  + size_out * (ins - 1)
208  + size_loop * (ins * outs - 1));
209  }
210 
213  std::vector<size_t> transition_cache_;
214  };
215  }
216 
217  /*------------------.
218  | eliminate_state. |
219  `------------------*/
220 
221  namespace detail
222  {
226  template <Automaton Aut, typename Profiler>
228  {
229  using profiler_t = Profiler;
230  using profile_t = typename profiler_t::state_profile;
231  using automaton_t = std::remove_cv_t<Aut>;
233 
239  : aut_(aut)
240  , profiler_(profiler)
242  {
243  for (auto s: aut_->states())
244  handles_[s] = todo_.emplace(profiler_.make_state_profile(s));
245  }
246 
249  {
250  if (s == aut_->null_state())
251  {
252  require(!todo_.empty(), "no state left to remove");
253  auto p = todo_.top();
254  todo_.pop();
255  s = p.state_;
256  }
257  else
258  require(aut_->has_state(s), "not a valid state: ", s);
259  eliminate_state_(s);
260  }
261 
263  void operator()()
264  {
265  while (!todo_.empty())
266  {
267  auto p = todo_.top();
268  todo_.pop();
269 
270 #ifdef DEBUG_LOOP
271  std::cerr << "Remove: " << p << '\n';
272 #endif
273  eliminate_state_(p.state_);
274  }
275  }
276 
277  private:
279  {
280 #ifdef DEBUG_UPDATE
281  std::cerr << "update heap: (";
282  show_heap_();
283 #endif
284  for (auto s: neighbors_)
285  if (s != aut_->pre() && s != aut_->post())
286  {
287  auto& h = handles_[s];
288  profiler_.update(*h);
289  todo_.update(h);
290  }
291 #ifdef DEBUG_UPDATE
292  std::cerr << ") => ";
293  show_heap_();
294  std::cerr << '\n';
295 #endif
296  }
297 
299  void show_heap_() const
300  {
301  const char* sep = "";
302  for (auto i = todo_.ordered_begin(), end = todo_.ordered_end();
303  i != end; ++i)
304  {
305  std::cerr << sep << *i;
306  sep = " > ";
307  }
308  }
309 
311  template <typename Kind = typename context_t_of<automaton_t>::kind_t>
313  -> std::enable_if_t<std::is_same<Kind, labels_are_one>::value,
314  void>
315  {
316  neighbors_.clear();
317 
318  // Shorthand to the labelset.
319  const auto& ls = *aut_->labelset();
320 
321  // Shorthand to the weightset.
322  const auto& ws = *aut_->weightset();
323 
324  // The loop's weight.
325  auto loop = ws.zero();
326  assert(outin(aut_, s, s).size() <= 1);
327  // There is a single possible loop labeled by \e, but it's
328  // easier and symmetrical with LAR to use a for-loop.
329  for (auto t: make_vector(outin(aut_, s, s)))
330  {
331  loop = ws.add(loop, aut_->weight_of(t));
332  aut_->del_transition(t);
333  }
334  loop = ws.star(loop);
335 
336  // Get all the predecessors, and successors, except itself.
337  auto outs = all_out(aut_, s);
338  for (auto in: all_in(aut_, s))
339  for (auto out: outs)
340  {
341  auto src = aut_->src_of(in);
342  auto dst = aut_->dst_of(out);
343  auto t = aut_->add_transition
344  (src, dst,
345  // Of course, most of the time \e\e => \e. But there
346  // is also $ to take into account when eliminating an
347  // initial/final state.
348  ls.mul(aut_->label_of(in), aut_->label_of(out)),
349  ws.mul(aut_->weight_of(in), loop, aut_->weight_of(out)));
350  profiler_.invalidate_cache(t);
351  neighbors_.emplace(src);
352  neighbors_.emplace(dst);
353  }
354 
355  aut_->del_state(s);
356  update_heap_();
357  }
358 
360  //
361  // FIXME: expressionset<lal_char(a-c), z>, q for instance cannot
362  // work, because we need to move the q weights inside the
363  // lal_char(a-c), z expressions, which obviously not possible.
364  // So we need to require that there is a subtype relationship
365  // between the weightset and the weightset of the expression.
366  //
367  // Yet as of 2014-07, there is no means to check that subtype
368  // relationship in Vcsn.
369  template <typename Kind>
371  -> std::enable_if_t<std::is_same<Kind, labels_are_expressions>::value,
372  void>
373  {
374  neighbors_.clear();
375 
376  // Shorthand to the labelset, which is an expressionset.
377  const auto& rs = *aut_->labelset();
378 
379  // The loops' expression.
380  auto loop = rs.zero();
381  for (auto t: make_vector(outin(aut_, s, s)))
382  {
383  loop = rs.add(loop,
384  rs.lweight(aut_->weight_of(t), aut_->label_of(t)));
385  aut_->del_transition(t);
386  }
387  loop = rs.star(loop);
388 
389  // Get all the predecessors, and successors, except itself.
390  auto outs = all_out(aut_, s);
391  for (auto in: all_in(aut_, s))
392  for (auto out: outs)
393  {
394  auto src = aut_->src_of(in);
395  auto dst = aut_->dst_of(out);
396  auto t = aut_->add_transition
397  (src, dst,
398  rs.mul(rs.lweight(aut_->weight_of(in), aut_->label_of(in)),
399  loop,
400  rs.lweight(aut_->weight_of(out), aut_->label_of(out))));
401  profiler_.invalidate_cache(t);
402  neighbors_.emplace(src);
403  neighbors_.emplace(dst);
404  }
405 
406  aut_->del_state(s);
407  update_heap_();
408  }
409 
414 
416  using heap_t = boost::heap::fibonacci_heap<profile_t>;
419  std::vector<typename heap_t::handle_type> handles_;
420 
421  std::unordered_set<state_t> neighbors_;
422  };
423 
424  template <Automaton Aut, typename Profiler>
426  make_state_eliminator(Aut& a, Profiler& profiler)
427  {
428  return state_eliminator<Aut, Profiler>(a, profiler);
429  }
430  }
431 
432 
434  template <Automaton Aut>
435  Aut&
437  state_t_of<Aut> s = Aut::element_type::null_state())
438  {
439  // Delgado profiler not fit for lao with non expression weightset.
440  auto profiler = detail::naive_profiler<Aut>(res);
441  auto eliminate_state = detail::make_state_eliminator(res, profiler);
442  eliminate_state(s);
443  return res;
444  }
445 
447  template <Automaton Aut>
448  auto
449  eliminate_state(const Aut& aut,
450  state_t_of<Aut> s = Aut::element_type::null_state())
452  {
453  // Get a copy, but be sure to keep the correspondance bw original
454  // state numbers and the new ones.
455  auto res = make_fresh_automaton<Aut>(aut);
456  auto copy = make_copier(aut, res);
457  copy();
458  if (s != aut->null_state())
459  {
460  require(aut->has_state(s), "not a valid state: ", s);
461  s = copy.state_map().at(s);
462  }
463  return eliminate_state_here(res, s);
464  }
465 
466 
467  /*-----------------------.
468  | dyn::eliminate_state. |
469  `-----------------------*/
470 
471  namespace dyn
472  {
473  namespace detail
474  {
476  template <Automaton Aut, typename Int>
477  automaton
478  eliminate_state(const automaton& aut, int state)
479  {
480  const auto& a = aut->as<Aut>();
481  using state_t = state_t_of<Aut>;
482  auto s = 0 <= state ? state_t(state + 2) : a->null_state();
483  return vcsn::eliminate_state(a, s);
484  }
485  }
486  }
487 
488 
489  /*----------------------------.
490  | to_expression(automaton). |
491  `----------------------------*/
492 
493  template <Automaton Aut,
494  typename Profiler,
495  typename ExpSet = expressionset<context_t_of<Aut>>>
496  typename ExpSet::value_t
497  to_expression(Aut& a, Profiler& profiler)
498  {
499  try
500  {
501  auto eliminate_states = detail::make_state_eliminator(a, profiler);
502  eliminate_states();
503  return a->get_initial_weight(a->post());
504  }
505  catch (const std::runtime_error& e)
506  {
507  raise(e, " while making expression");
508  }
509  }
510 
512  {
513  best,
514  delgado,
516  naive,
517  };
518 
519  template <Automaton Aut,
520  typename ExpSet = expressionset<context_t_of<Aut>>>
521  typename ExpSet::value_t
524  {
525  // State elimination is performed on the lifted automaton.
526  auto a = lift(aut, ids);
527  using delgado_t = detail::delgado_profiler<decltype(a)>;
528  using naive_t = detail::naive_profiler<decltype(a)>;
529  switch (algo)
530  {
532  raise("next_state: invalid algorithm: best");
533 
535  {
536  auto profiler = delgado_t(a);
537  return to_expression<decltype(a), delgado_t, ExpSet>(a, profiler);
538  }
539 
541  {
542  auto profiler = delgado_t(a, true);
543  return to_expression<decltype(a), delgado_t, ExpSet>(a, profiler);
544  }
545 
547  {
548  auto profiler = naive_t(a);
549  return to_expression<decltype(a), naive_t, ExpSet>(a, profiler);
550  }
551  }
553  }
554 
555  template <Automaton Aut,
556  typename ExpSet = expressionset<context_t_of<Aut>>>
557  typename ExpSet::value_t
560  {
562  {
563  typename ExpSet::value_t best;
564  auto best_size = std::numeric_limits<size_t>::max();
568  {
569  auto r = to_expression_heuristic<Aut, ExpSet>(aut, ids, a);
570  auto s = rat::size<ExpSet>(r);
571  if (s < best_size)
572  {
573  best = r;
574  best_size = s;
575  }
576  }
577  return best;
578  }
579  else
580  {
581  return to_expression_heuristic<Aut, ExpSet>(aut, ids, algo);
582  }
583  }
584 
585  template <Automaton Aut,
586  typename ExpSet = expressionset<context_t_of<Aut>>>
587  typename ExpSet::value_t
589  const std::string& algo)
590  {
591  static const auto map = getarg<to_expression_heuristic_t>
592  {
593  "heuristics",
594  {
595  {"auto", "best"},
598  {"delgado_label", to_expression_heuristic_t::delgado_label},
600  }
601  };
602  return to_expression<Aut, ExpSet>(a, ids, map[algo]);
603  }
604 
605  /*----------------------------.
606  | to_expression(automaton). |
607  `----------------------------*/
608 
609  namespace dyn
610  {
611  namespace detail
612  {
614  template <Automaton Aut, typename Identities, typename String>
615  expression
616  to_expression(const automaton& aut, identities ids,
617  const std::string& algo)
618  {
619  const auto& a = aut->as<Aut>();
620  using context_t = context_t_of<Aut>;
621  using expressionset_t = vcsn::expressionset<context_t>;
622  auto rs = expressionset_t{a->context(), ids};
623  auto res = ::vcsn::to_expression(a, ids, algo);
624  return {rs, res};
625  }
626  }
627  }
628 
629  /*------------------------.
630  | to_expression(label). |
631  `------------------------*/
632 
633  namespace dyn
634  {
635  namespace detail
636  {
638  template <typename Context, typename Identities, typename Label>
639  expression
640  to_expression_label(const context& ctx, identities ids,
641  const label& lbl)
642  {
643  const auto& c = ctx->as<Context>();
644  const auto& l = lbl->as<Label>();
645  auto rs = vcsn::make_expressionset(c, ids);
646  return {rs, rs.atom(l.value())};
647  }
648  }
649  }
650 
651 
652  /*-------------------------------.
653  | to_expression(letter_class). |
654  `-------------------------------*/
655 
656  namespace detail
657  {
658  template <typename ExpSet>
659  auto letter_class_impl(const ExpSet&,
660  const letter_class_t&, bool,
661  std::false_type, std::true_type)
662  -> typename ExpSet::value_t
663  {
664  raise("letter_class: not implemented (is_expressionset)");
665  }
666 
667  template <typename ExpSet>
668  auto letter_class_impl(const ExpSet& rs,
669  const letter_class_t& chars, bool accept,
670  std::false_type, std::false_type)
671  -> typename ExpSet::value_t
672  {
673  auto ls = *rs.labelset();
674 
675  using labelset_t = decltype(ls);
676  using letter_t = typename labelset_t::letter_t;
677 
678  auto ccs = std::set<std::pair<letter_t, letter_t>>{};
679  for (const auto& cc: chars)
680  {
681  std::istringstream i1{cc.first};
682  std::istringstream i2{cc.second};
683  letter_t l1 = ls.get_letter(i1, false);
684  letter_t l2 = ls.get_letter(i2, false);
685  ccs.emplace(l1, l2);
686  }
687  return rs.letter_class(ccs, accept);
688  }
689 
690  template <typename ExpSet>
691  auto letter_class_impl(const ExpSet& rs,
692  const letter_class_t&, bool,
693  std::true_type, std::false_type)
694  -> typename ExpSet::value_t
695  {
696  return rs.one();
697  }
698  }
699 
709  template <typename ExpressionSet>
710  typename ExpressionSet::value_t
711  to_expression(const ExpressionSet& rs, const letter_class_t& letters,
712  bool accept = true)
713  {
714  using labelset_t = labelset_t_of<ExpressionSet>;
715  using is_one_t = std::is_same<labelset_t, vcsn::oneset>;
717  return detail::letter_class_impl(rs, letters, accept,
718  is_one_t{}, is_expset_t{});
719  }
720 
721  namespace dyn
722  {
723  namespace detail
724  {
726  template <typename Context, typename Identities,
727  typename Letters, typename Bool>
728  expression
729  to_expression_class(const context& ctx, identities ids,
730  const letter_class_t& letters, bool accept)
731  {
732  const auto& c = ctx->as<Context>();
733  auto rs = vcsn::make_expressionset(c, ids);
734  return {rs, to_expression(rs, letters, accept)};
735  }
736  }
737  }
738 } // vcsn::
state_profile make_state_profile(state_t state)
detail::lifted_automaton_t< Aut, Tapes... > lift(const Aut &a, vcsn::rat::identities ids={})
Lift some tapes of the transducer.
Definition: lift.hh:215
to_expression_heuristic_t
ExpSet::value_t to_expression_heuristic(const Aut &aut, vcsn::rat::identities ids, to_expression_heuristic_t algo)
std::unordered_set< state_t > neighbors_
naive_profiler(const automaton_t &aut)
#define Automaton
Definition: automaton.hh:23
state_eliminator< Aut, Profiler > make_state_eliminator(Aut &a, Profiler &profiler)
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
std::remove_cv_t< Aut > automaton_t
delgado_profiler(const automaton_t &aut, bool count_labels=false)
Build a generator of Delgado-Morais state profiles.
std::vector< typename heap_t::handle_type > handles_
Map: state -> heap-handle.
The state profile is the product of the number of (strictly) incoming transitions with the number of ...
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
Compute a state profile for state-elimination based on connectivity.
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
state_t_of< automaton_t > state_t
transition_t_of< automaton_t > transition_t
void show_heap_() const
Show the heap, for debugging.
size_t size_of_transition(transition_t t)
The "weight" of a transition.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
size_t states_size(const Aut &aut)
The largest state number, plus one.
Definition: automaton.hh:19
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:113
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
size_t size_
Number of strictly incoming transitions, times the number of strictly outgoing transitions.
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:64
std::vector< size_t > transition_cache_
automaton eliminate_state(const automaton &aut, int state)
Bridge.
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
size_t transitions_size(const Aut &aut)
The largest transition number, plus one.
Definition: automaton.hh:29
auto & as()
Downcast to the exact type.
Definition: context.hh:36
void update(state_profile &p)
The "weight" of a state, as defined by Delgado-Morais.
A dyn Value/ValueSet.
Definition: fwd.hh:23
auto outin(const Aut &aut, state_t_of< Aut > s, state_t_of< Aut > d)
Indexes of visible transitions from state s to state d.
Definition: automaton.hh:167
return res
Definition: multiply.hh:398
profiler_t & profiler_
The profiler we work with. Corresponding to a specific heuristic.
transition_t_of< automaton_t > transition_t
auto letter_class_impl(const ExpSet &, const letter_class_t &, bool, std::false_type, std::true_type) -> typename ExpSet::value_t
auto eliminate_state(const Aut &aut, state_t_of< Aut > s=Aut::element_type::null_state()) -> fresh_automaton_t_of< Aut >
A copy of automaton res without the state s.
expression to_expression(const automaton &aut, identities ids={}, const std::string &algo="auto")
An expression denoting the language of aut.
bool operator<(const state_profile &rhs) const
bool operator<(const state_profile &rhs) const
void operator()()
Eliminate all the states, in the order specified by next_state.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
expression to_expression_class(const context &ctx, identities ids, const letter_class_t &letters, bool accept)
Bridge (to_expression).
void invalidate_cache(transition_t t)
Updating transitions' size in the cache during the profiler's construction would be clearer but appea...
Template-less root for contexts.
Definition: context.hh:16
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
Definition: copy.hh:322
auto rs
Definition: lift.hh:152
Definition: a-star.hh:8
state_t_of< automaton_t > state_t
A dyn automaton.
Definition: automaton.hh:17
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
Definition: traits.hh:82
friend std::ostream & operator<<(std::ostream &o, const state_profile &p)
An expressionset can implement several different sets of identities on expressions.
Definition: identities.hh:21
state_t_of< automaton_t > state_t
friend std::ostream & operator<<(std::ostream &o, const state_profile &p)
auto eliminate_state_(state_t s) -> std::enable_if_t< std::is_same< Kind, labels_are_one >::value, void >
Eliminate state s in the case of labels are one.
auto all_in(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions entering state s.
Definition: automaton.hh:94
automaton_t aut_
The automaton we work on.
auto letter_class_impl(const ExpSet &rs, const letter_class_t &, bool, std::true_type, std::false_type) -> typename ExpSet::value_t
expression to_expression_label(const context &ctx, identities ids, const label &lbl)
Bridge (to_expression).
state_eliminator(automaton_t &aut, profiler_t &profiler)
Prepare for state-elimination.
detail::copier< AutIn, AutOut > make_copier(const AutIn &in, AutOut &out, bool safe=true)
Build an automaton copier.
Definition: copy.hh:256
Aut & eliminate_state_here(Aut &res, state_t_of< Aut > s=Aut::element_type::null_state())
In place removal of state s from automaton res.
expression to_expression(const automaton &aut, identities ids, const std::string &algo)
Bridge.
auto make_expressionset(const context< LabelSet, WeightSet > &ctx, rat::identities ids={}) -> expressionset< context< LabelSet, WeightSet >>
Shorthand to expressionset constructor.
Compute a state profile for state-elimination based on the Delgado-Morais heuristic.
auto eliminate_state_impl_(state_t s) -> std::enable_if_t< std::is_same< Kind, labels_are_expressions >::value, void >
Eliminate state s in the case of labels are expressions.
std::set< std::pair< std::string, std::string >> letter_class_t
A set of letter ranges.
Definition: fwd.hh:111
void invalidate_cache(transition_t)
auto & as()
Extract wrapped typed value.
Definition: value.hh:53
typename profiler_t::state_profile profile_t
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
state_profile make_state_profile(state_t state)
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
Eliminate states in an automaton.
A mapping from strings to Values.
Definition: getargs.hh:33
static identities ids(const driver &d)
Get the identities of the driver.
Definition: parse.cc:89
void update(state_profile &p)
std::integral_constant< bool, B > bool_constant
Definition: type_traits.hh:12
ExpressionSet::value_t to_expression(const ExpressionSet &rs, const letter_class_t &letters, bool accept=true)
An expression matching one letter in a letter class.
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
void operator()(state_t s)
Eliminate state s.
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
ExpSet::value_t to_expression(Aut &a, Profiler &profiler)
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
boost::heap::fibonacci_heap< profile_t > heap_t
Max-heap to decide the order of state-elimination.