Vcsn  2.3a
Be Rational
conjunction.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <iostream>
4 #include <map>
5 #include <utility>
6 
7 #include <vcsn/algos/copy.hh>
8 #include <vcsn/algos/insplit.hh>
10 #include <vcsn/algos/strip.hh>
11 #include <vcsn/algos/tags.hh>
12 #include <vcsn/algos/transpose.hh>
17 #include <vcsn/ctx/context.hh>
18 #include <vcsn/ctx/traits.hh>
19 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
20 #include <vcsn/dyn/value.hh>
21 #include <vcsn/misc/set.hh> // has
22 #include <vcsn/misc/static-if.hh>
23 #include <vcsn/misc/to.hh>
24 #include <vcsn/misc/tuple.hh> // tuple_element_t, cross_tuple
25 #include <vcsn/misc/zip-maps.hh>
26 
27 namespace vcsn
28 {
29  namespace detail
30  {
31  /*---------------------------------.
32  | product_automaton_impl<Aut...>. |
33  `---------------------------------*/
34 
36  template <bool Lazy, Automaton Aut, Automaton... Auts>
38  : public lazy_tuple_automaton<product_automaton_impl<Lazy, Aut, Auts...>,
39  false, Lazy, Aut, Auts...>
40  {
41  static_assert(all_<labelset_t_of<Auts>::is_letterized()...>(),
42  "product: requires letterized labels");
43 
45  using automaton_t = Aut;
47  using super_t = lazy_tuple_automaton<self_t, false, Lazy, Aut, Auts...>;
48 
49  public:
51  using state_t = typename super_t::state_t;
52 
53  template <Automaton A>
54  using transition_map_t = typename super_t::template transition_map_t<A>;
55 
56  template <size_t... I>
57  using seq = typename super_t::template seq<I...>;
58 
59  using super_t::ws_;
61 
62  static symbol sname()
63  {
64  static symbol res("product_automaton"
65  + super_t::sname_(std::string{Lazy ? "true" : "false"}));
66  return res;
67  }
68 
69  std::ostream& print_set(std::ostream& o, format fmt = {}) const
70  {
71  o << "product_automaton";
72  return aut_->print_set_(o, fmt);
73  }
74 
79 
80  using label_t = typename labelset_t::value_t;
81  using weight_t = typename weightset_t::value_t;
82 
84  using automata_t = std::tuple<Auts...>;
85 
87  template <size_t I>
89 
90  using super_t::aut_;
91 
95  product_automaton_impl(Aut aut, const Auts&... auts)
96  : super_t{aut, auts...}
97  {}
98 
100  void conjunction()
101  {
103 
104  if (!Lazy)
105  while (!aut_->todo_.empty())
106  {
107  const auto& p = aut_->todo_.front();
108  add_conjunction_transitions(std::get<1>(p), std::get<0>(p));
109  aut_->todo_.pop_front();
110  }
111  }
112 
114  template <bool L = Lazy>
115  std::enable_if_t<sizeof...(Auts) == 2 && !L> ldivide()
116  {
117  static_assert(labelset_t::has_one(),
118  "ldivide: labelset must have a neutral");
120 
121  while (!aut_->todo_.empty())
122  {
123  const auto& p = aut_->todo_.front();
124  add_ldivide_transitions(std::get<1>(p), std::get<0>(p));
125  aut_->todo_.pop_front();
126  }
127  }
128 
130  template <bool L = Lazy>
131  std::enable_if_t<sizeof...(Auts) == 2 && !L> add()
132  {
133  using lhs_t = input_automaton_t<0>;
134  using rhs_t = input_automaton_t<1>;
135  constexpr bool bb = (std::is_same<weightset_t_of<lhs_t>, b>::value
136  && std::is_same<weightset_t_of<rhs_t>, b>::value);
137  static_assert(bb, "add: requires Boolean weightset");
139 
140  while (!aut_->todo_.empty())
141  {
142  const auto& p = aut_->todo_.front();
143  add_add_transitions(std::get<1>(p), std::get<0>(p));
144  aut_->todo_.pop_front();
145  }
146  }
147 
149  template <bool L = Lazy>
150  std::enable_if_t<sizeof...(Auts) == 2 && !L> ldivide_here()
151  {
153 
154  using rhs_t = input_automaton_t<1>;
155  auto new_initials = std::vector<state_t_of<rhs_t>>();
156 
157  const auto& lhs = std::get<0>(aut_->auts_);
158  auto& rhs = std::get<1>(aut_->auts_);
159 
160  while (!aut_->todo_.empty())
161  {
162  const auto& p = aut_->todo_.front();
163  const auto& state_name = std::get<0>(p);
164  add_conjunction_transitions(std::get<1>(p), state_name);
165 
166  // If lhs's state is final, rhs's corresponding state is initial.
167  if (lhs->is_final(std::get<0>(state_name)))
168  new_initials.push_back(std::get<1>(state_name));
169  aut_->todo_.pop_front();
170  }
171 
172  for (auto t: initial_transitions(rhs))
173  rhs->unset_initial(rhs->dst_of(t));
174  for (auto s: new_initials)
175  rhs->set_initial(s);
176  }
177 
179  void shuffle()
180  {
181  // Issue #86.
182  if (!std::is_same<weightset_t, b>{})
183  {
184  require(is_proper(std::get<0>(aut_->auts_)),
185  "shuffle: invalid lhs:"
186  " weighted automata with spontaneous"
187  " transitions are not supported");
188  require(is_proper(std::get<1>(aut_->auts_)),
189  "shuffle: invalid rhs:"
190  " weighted automata with spontaneous"
191  " transitions are not supported");
192  }
193 
195 
196  while (!aut_->todo_.empty())
197  {
198  const auto& p = aut_->todo_.front();
199  add_shuffle_transitions<false>(std::get<1>(p), std::get<0>(p));
200  aut_->todo_.pop_front();
201  }
202  }
203 
205  void infiltrate()
206  {
207  // Variadic infiltrate is not trivial to implement, it's not
208  // just conjunction and shuffle in series. For instance, consider
209  // three automata:
210  //
211  // <x>a
212  // x = -> 0 ------> 1 ->
213  //
214  // and likewise for y and z. Let's use `&:` to denote
215  // infiltrate. In (x &: y) there is a transition ((0,0),
216  // <xy>a, (1,1)) coming from the conjunction-like transitions.
217  //
218  // Therefore in (x &: y) &: z there is a transition ((0,0),0),
219  // <xy>a, (1,1), 0) by virtue of the shuffle-like transitions.
220  //
221  // This kind of transition that mixes conjunction and shuffle
222  // would never appear in a naive implementation with only
223  // conjunction and shuffle transitions, but no combinations.
224  require(sizeof...(Auts) == 2,
225  "infiltrate: variadic product does not work");
226 
227  // Issue #86.
228  if (!std::is_same<weightset_t, b>{})
229  {
230  require(is_proper(std::get<0>(aut_->auts_)),
231  "infiltrate: invalid lhs:"
232  " weighted automata with spontaneous"
233  " transitions are not supported");
234  require(is_proper(std::get<1>(aut_->auts_)),
235  "infiltrate: invalid rhs:"
236  " weighted automata with spontaneous"
237  " transitions are not supported");
238  }
239 
240  // Infiltrate is a mix of conjunction and shuffle operations, and
241  // the initial states for shuffle are a superset of the
242  // initial states for conjunction:
244 
245  while (!aut_->todo_.empty())
246  {
247  const auto& p = aut_->todo_.front();
248  // Infiltrate is a mix of conjunction and shuffle operations.
249  //
250  // Conjunction transitions must be added before shuffle ones:
251  // this way "conjunction" can use "new_transition" only, which
252  // is faster than "add_transition".
253  add_conjunction_transitions(std::get<1>(p), std::get<0>(p));
254  add_shuffle_transitions<true>(std::get<1>(p), std::get<0>(p));
255 
256  aut_->todo_.pop_front();
257  }
258  }
259 
261  void add_transitions(const state_t src,
262  const state_name_t& psrc)
263  {
264  add_conjunction_transitions(src, psrc);
265  }
266 
267  private:
271  {
272  aut_->todo_.emplace_back(aut_->pre_(), aut_->pre());
273  }
274 
278  {
279  // Make the result automaton initial states: same as the
280  // conjunction of pre: synchronized transitions on $.
281  add_conjunction_transitions(aut_->pre(), aut_->pre_());
282  }
283 
284  using super_t::out_;
285  using super_t::state;
291  const state_name_t& psrc)
292  {
293  for (const auto& t: zip_map_tuple(out_(psrc)))
294  // These are always new transitions: first because the
295  // source state is visited for the first time, and second
296  // because the couple (left destination, label) is unique,
297  // and so is (right destination, label).
298  if (!aut_->labelset()->is_one(t.first))
300  ([this,src,&t]
301  (const typename transition_map_t<Auts>::transition&... ts)
302  {
303  this->new_transition(src, state(ts.dst...),
304  t.first,
305  ws_.mul(ts.weight()...));
306  },
307  t.second);
308  add_one_transitions_(src, psrc, aut_->indices);
309  }
310 
317  template <bool L = Lazy>
318  std::enable_if_t<sizeof...(Auts) == 2 && !L>
320  {
321  const auto& ls = *aut_->labelset();
322  const auto& lhs = std::get<0>(aut_->auts_);
323  const auto& rhs = std::get<1>(aut_->auts_);
324  const auto& lstate = std::get<0>(psrc);
325  const auto& rstate = std::get<1>(psrc);
326 
327  if (lhs->is_final(lstate) || lstate == lhs->post())
328  {
329  for (auto ts: all_out(rhs, rstate))
330  {
331  const auto& lweight = lhs->is_final(lstate)
332  ? lhs->get_final_weight(lstate) : ws_.one();
333  this->new_transition(src,
334  state(lhs->post(), rhs->dst_of(ts)),
335  rhs->label_of(ts),
336  ws_.ldivide(lweight, rhs->weight_of(ts)));
337  }
338  }
339  for (const auto& t: zip_map_tuple(out_(psrc)))
340  if (!ls.is_one(t.first)
341  && (!ls.is_special(t.first) || src == aut_->pre()))
343  ([this,ls,src,t]
344  (const typename transition_map_t<Auts>::transition&... ts)
345  {
346  this->add_transition(src, state(ts.dst...),
347  ls.is_special(t.first)
348  ? t.first : ls.one(),
349  ws_.ldivide(ts.weight()...));
350  },
351  t.second);
352  }
353 
357  template <bool L = Lazy>
358  std::enable_if_t<sizeof...(Auts) == 2 && !L>
359  add_add_transitions(const state_t src, const state_name_t& psrc)
360  {
361  const auto& lhs = std::get<0>(aut_->auts_);
362  const auto& rhs = std::get<1>(aut_->auts_);
363  const auto& lstate = std::get<0>(psrc);
364  const auto& rstate = std::get<1>(psrc);
365 
366  auto common_labels = std::set<label_t_of<Aut>>{};
367  for (auto t: zip_map_tuple(out_(psrc)))
368  {
369  common_labels.insert(t.first);
371  ([this,src,t]
372  (const typename transition_map_t<Auts>::transition&... ts)
373  {
374  this->add_transition(src, state(ts.dst...), t.first);
375  },
376  t.second);
377  }
378  for (auto t: all_out(lhs, lstate))
379  if (!has(common_labels, lhs->label_of(t)))
380  this->new_transition(src, state(lhs->dst_of(t), rhs->post()),
381  lhs->label_of(t));
382  for (auto t: all_out(rhs, rstate))
383  if (!has(common_labels, rhs->label_of(t)))
384  this->new_transition(src, state(lhs->post(), rhs->dst_of(t)),
385  rhs->label_of(t));
386  }
387 
390  template <std::size_t... I>
391  void
392  add_one_transitions_(const state_t src, const state_name_t& psrc,
393  seq<I...>)
394  {
395  using swallow = int[];
396  (void) swallow
397  {
398  (add_one_transitions_<I>(*(std::get<I>(aut_->auts_)->labelset()),
399  src, psrc), 0)...
400  };
401  }
402 
404  template <std::size_t I, typename LS>
405  std::enable_if_t<!LS::has_one(), void>
406  add_one_transitions_(const LS&, const state_t, const state_name_t&)
407  {}
408 
411  template <std::size_t I, typename LS>
412  std::enable_if_t<LS::has_one(), void>
413  add_one_transitions_(const LS& ls, const state_t src,
414  const state_name_t& psrc)
415  {
416  // The first condition prevents the creation of redundant
417  // paths that would lead to incorrect valuations (in the
418  // weighted case), while the second is purely an optimization,
419  // avoiding the creation of non-coaccessible states.
420  if (are_proper_in(psrc, make_index_range<I + 1, sizeof...(Auts)>{})
422  {
423  // one is guaranteed to be first.
424  const auto& tmap = std::get<I>(transition_maps_)[std::get<I>(psrc)];
425  if (!tmap.empty() && ls.is_one(tmap.begin()->first))
426  for (auto t : tmap.begin()->second)
427  {
428  auto pdst = psrc;
429  std::get<I>(pdst) = t.dst;
430  this->new_transition(src, state(pdst), ls.one(), t.weight());
431  }
432  }
433  }
434 
437  template <std::size_t... I>
438  bool are_proper_in(const state_name_t& psrc, seq<I...>) const
439  {
440  return all(is_proper_in<I>(psrc)...);
441  }
442 
445  template <std::size_t... I>
447  {
448  return all(has_proper_out<I>(psrc)...);
449  }
450 
453  template <Automaton Aut_>
454  std::enable_if_t<labelset_t_of<Aut_>::has_one(), bool>
455  is_one(const Aut_& aut, transition_t_of<Aut_> tr) const
456  {
457  return aut->labelset()->is_one(aut->label_of(tr));
458  }
459 
462  template <Automaton Aut_>
463  constexpr std::enable_if_t<!labelset_t_of<Aut_>::has_one(), bool>
464  is_one(const Aut_&, transition_t_of<Aut_>) const
465  {
466  return false;
467  }
468 
470  template <size_t I>
471  constexpr auto
473  -> std::enable_if_t<!labelset_t_of<input_automaton_t<I>>::has_one(),
474  bool>
475  {
476  return true;
477  }
478 
483  template <size_t I>
484  auto
485  is_proper_in(const state_name_t& sn) const
486  -> std::enable_if_t<labelset_t_of<input_automaton_t<I>>::has_one(),
487  bool>
488  {
489  // Amusingly enough, it is faster to check the incoming
490  // transitions rather than recovering the decoration of the
491  // insplit state, which tells whether the state is proper-in.
492  const auto& aut = std::get<I>(aut_->auts_);
493  auto s = std::get<I>(sn);
494  auto rin = all_in(aut, s);
495  auto rtr = rin.begin();
496  // Insplit state, so checking the first transition suffices.
497  // There can be no incoming transitions in the case of pre.
498  return rtr == rin.end() || !is_one(aut, *rtr);
499  }
500 
506  template <size_t I>
507  bool
509  {
510  const auto& tmap = std::get<I>(transition_maps_)[std::get<I>(psrc)];
511  auto s = tmap.size();
512  if (s == 0)
513  return false;
514  else if (2 <= s)
515  return true;
516  else
517  return !std::get<I>(aut_->auts_)->labelset()->is_one(tmap.begin()->first);
518  }
519 
524  template <bool Infiltrate = false>
526  const state_name_t& psrc)
527  {
528  weight_t final
529  = add_shuffle_transitions_<Infiltrate>(src, psrc, aut_->indices);
530  aut_->set_final(src, final);
531  }
532 
537  template <bool Infiltrate, size_t... I>
539  const state_name_t& psrc,
540  seq<I...>)
541  {
542  weight_t res = ws_.one();
543  using swallow = int[];
544  (void) swallow
545  {
546  (res = ws_.mul(res,
547  add_shuffle_transitions_<Infiltrate, I>(src, psrc)),
548  0)...
549  };
550  return res;
551  }
552 
563  template <bool Infiltrate, size_t I>
564  weight_t
566  const state_name_t& psrc)
567  {
568  // Whether is a final state.
569  weight_t res = ws_.zero();
570 
571  auto& ts = std::get<I>(transition_maps_)[std::get<I>(psrc)];
572  for (auto t: ts)
573  if (std::get<I>(aut_->auts_)->labelset()->is_special(t.first))
574  res = t.second.front().weight();
575  else
576  // The src state is visited for the first time, so all
577  // these transitions are new. *Except* in the case where
578  // we have a loop on some tapes.
579  //
580  // If add_conjunction_transitions was called before (in the
581  // case of infiltrate), there may even exist such a
582  // transition in the first loop.
583  //
584  // To trigger the later case, try the self-infiltrate on
585  // derived_term('a*a').
586  for (auto d: t.second)
587  {
588  auto pdst = psrc;
589  std::get<I>(pdst) = d.dst;
590  if (Infiltrate
591  || std::get<I>(psrc) == d.dst)
592  this->add_transition(src, state(pdst), t.first, d.weight());
593  else
594  this->new_transition(src, state(pdst), t.first, d.weight());
595  }
596  return res;
597  }
598  };
599 
601  template <bool Lazy, Automaton Aut, Automaton... Auts>
602  using product_automaton
603  = std::shared_ptr<detail::product_automaton_impl<Lazy, Aut, Auts...>>;
604 
605  template <bool Lazy, Automaton Aut, Automaton... Auts>
606  auto
607  make_product_automaton(Aut aut, const Auts&... auts)
608  -> product_automaton<Lazy, Aut, Auts...>
609  {
610  using res_t = product_automaton<Lazy, Aut, Auts...>;
611  return make_shared_ptr<res_t>(aut, auts...);
612  }
613 
614 
615  /*-----------------------------.
616  | conjunction(automaton...). |
617  `-----------------------------*/
618 
620  template <Automaton Aut, Automaton... Auts>
621  auto
622  conjunction(const Aut& a, const Auts&... as)
623  {
624  auto res = make_product_automaton<false>(meet_automata(a, as...),
625  a, insplit(as)...);
626  res->conjunction();
627  return res->strip();
628  }
629 
631  template <Automaton Aut, Automaton... Auts>
632  auto
633  conjunction_lazy(const Aut& a, const Auts&... as)
634  {
635  auto res = make_product_automaton<true>(meet_automata(a, as...),
636  a, insplit(as)...);
637  res->conjunction();
638  return res;
639  }
640  }
641 
642  using detail::conjunction;
644 
645  namespace dyn
646  {
647  namespace detail
648  {
650  template <typename Auts, size_t... I>
651  automaton
652  conjunction_(const std::vector<automaton>& as, bool lazy,
654  {
655  if (lazy)
656  return conjunction_lazy(as[I]->as<tuple_element_t<I, Auts>>()...);
657  else
658  return conjunction(as[I]->as<tuple_element_t<I, Auts>>()...);
659  }
660 
662  template <typename Auts, typename Bool>
663  automaton
664  conjunction(const std::vector<automaton>& as, bool lazy)
665  {
666  auto indices
668  return conjunction_<Auts>(as, lazy, indices);
669  }
670  }
671  }
672 
673 
674  /*---------------------------------.
675  | ldivide(automaton, automaton). |
676  `---------------------------------*/
677 
682  template <Automaton Aut1, Automaton Aut2>
683  auto
684  ldivide(const Aut1& lhs, const Aut2& rhs, auto_tag = {})
685  {
686  return detail::static_if<std::is_same<weightset_t_of<Aut1>, b>::value
687  && std::is_same<weightset_t_of<Aut2>, b>::value>
688  ([] (const auto& lhs, const auto& rhs)
689  {
690  return ldivide(lhs, rhs, boolean_tag{});
691  },
692  [] (const auto& lhs, const auto& rhs)
693  {
694  return ldivide(lhs, rhs, weighted_tag{});
695  }
696  )(lhs, rhs);
697  }
698 
699  template <Automaton Aut1, Automaton Aut2>
700  auto
701  ldivide(const Aut1& lhs, const Aut2& rhs, boolean_tag)
702  {
703  auto res =
704  detail::static_if<labelset_t_of<Aut2>::has_one()>
705  ([](const auto& rhs){ return insplit(rhs); },
706  [](const auto& rhs){ return copy(rhs); })
707  (rhs);
708  auto prod =
709  detail::make_product_automaton<false>(join_automata(lhs, res), lhs, res);
710  prod->ldivide_here();
711  return res;
712  }
713 
714  template <Automaton Aut1, Automaton Aut2>
715  auto
716  ldivide(const Aut1& lhs, const Aut2& rhs, weighted_tag)
717  {
718  auto prod =
719  detail::make_product_automaton<false>(join_automata(lhs, rhs), lhs, rhs);
720  prod->ldivide();
721  return prod->strip();
722  }
723 
724 
725  namespace dyn
726  {
727  namespace detail
728  {
730  template <Automaton Aut1, Automaton Aut2>
731  automaton
732  ldivide(const automaton& aut1, const automaton& aut2)
733  {
734  const auto& a1 = aut1->as<Aut1>();
735  const auto& a2 = aut2->as<Aut2>();
736  return vcsn::ldivide<Aut1, Aut2>(a1, a2);
737  }
738  }
739  }
740 
741 
742 
743  /*---------------------------------.
744  | rdivide(automaton, automaton). |
745  `---------------------------------*/
746 
751  template <Automaton Aut1, Automaton Aut2>
752  auto
753  rdivide(const Aut1& a1, const Aut2& a2)
754  {
755  auto a1t = transpose(a1);
756  auto a2t = transpose(a2);
757  return transpose(ldivide(a2t, a1t));
758  }
759 
760  namespace dyn
761  {
762  namespace detail
763  {
765  template <Automaton Aut1, Automaton Aut2>
766  automaton
767  rdivide(const automaton& aut1, const automaton& aut2)
768  {
769  const auto& a1 = aut1->as<Aut1>();
770  const auto& a2 = aut2->as<Aut2>();
771  return vcsn::rdivide(a1, a2);
772  }
773  }
774  }
775 
776 
777  /*------------------------.
778  | shuffle(automaton...). |
779  `------------------------*/
780 
782  template <Automaton... Auts>
783  auto
784  shuffle(const Auts&... as)
785  // SFINAE
786  -> tuple_automaton<decltype(join_automata(as...)),
787  Auts...>
788  {
789  auto res =
790  detail::make_product_automaton<false>(join_automata(as...), as...);
791  res->shuffle();
792  return res->strip();
793  }
794 
795  namespace dyn
796  {
797  namespace detail
798  {
800  template <typename Auts, size_t... I>
801  automaton
802  shuffle_(const std::vector<automaton>& as,
804  {
805  return vcsn::shuffle(as[I]->as<tuple_element_t<I, Auts>>()...);
806  }
807 
809  template <typename Auts>
810  automaton
811  shuffle(const std::vector<automaton>& as)
812  {
813  auto indices
815  return shuffle_<Auts>(as, indices);
816  }
817  }
818  }
819 
820 
821  /*-----------------------------------.
822  | shuffle(expression, expression). |
823  `-----------------------------------*/
824 
826  template <typename ValueSet>
827  typename ValueSet::value_t
828  shuffle(const ValueSet& vs,
829  const typename ValueSet::value_t& lhs,
830  const typename ValueSet::value_t& rhs)
831  {
832  return vs.shuffle(lhs, rhs);
833  }
834 
835  namespace dyn
836  {
837  namespace detail
838  {
840  template <typename ExpSetLhs, typename ExpSetRhs>
841  expression
842  shuffle_expression(const expression& lhs, const expression& rhs)
843  {
844  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
845  return {std::get<0>(join_elts),
846  ::vcsn::shuffle(std::get<0>(join_elts),
847  std::get<1>(join_elts),
848  std::get<2>(join_elts))};
849  }
850  }
851  }
852 
853 
854  /*----------------------------.
855  | infiltrate(automaton...). |
856  `----------------------------*/
857 
859  template <Automaton A1, Automaton A2>
860  auto
861  infiltrate(const A1& a1, const A2& a2)
862  -> tuple_automaton<decltype(join_automata(a1, a2)),
863  A1, A2>
864  {
865  auto res =
866  detail::make_product_automaton<false>(join_automata(a1, a2), a1, a2);
867  res->infiltrate();
868  return res->strip();
869  }
870 
872  template <Automaton A1, Automaton A2, Automaton A3, Automaton... Auts>
873  auto
874  infiltrate(const A1& a1, const A2& a2, const A3& a3, const Auts&... as)
875  // SFINAE
876  -> decltype(infiltrate(infiltrate(a1, a2), a3, as...))
877  {
878  return infiltrate(infiltrate(a1, a2), a3, as...);
879  }
880 
881  namespace dyn
882  {
883  namespace detail
884  {
886  template <typename Auts, size_t... I>
887  automaton
888  infiltrate_(const std::vector<automaton>& as,
890  {
891  return vcsn::infiltrate(as[I]->as<tuple_element_t<I, Auts>>()...);
892  }
893 
895  template <typename Auts>
896  automaton
897  infiltrate(const std::vector<automaton>& as)
898  {
899  auto indices
901  return infiltrate_<Auts>(as, indices);
902  }
903  }
904  }
905 
906  /*--------------------------------------.
907  | infiltrate(expression, expression). |
908  `--------------------------------------*/
909 
911  template <typename ValueSet>
912  typename ValueSet::value_t
913  infiltrate(const ValueSet& vs,
914  const typename ValueSet::value_t& lhs,
915  const typename ValueSet::value_t& rhs)
916  {
917  return vs.infiltrate(lhs, rhs);
918  }
919 
920  namespace dyn
921  {
922  namespace detail
923  {
925  template <typename ExpSetLhs, typename ExpSetRhs>
926  expression
928  {
929  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
930  return {std::get<0>(join_elts),
931  ::vcsn::infiltrate(std::get<0>(join_elts),
932  std::get<1>(join_elts),
933  std::get<2>(join_elts))};
934  }
935  }
936  }
937 
938 
939  /*-----------------------------.
940  | conjunction(automaton, n). |
941  `-----------------------------*/
942 
949  template <Automaton Aut>
950  auto
951  conjunction(const Aut& aut, to exp)
953  {
954  // We used to compute `a & n` as `([^]* & a) & a)...`. The code
955  // was simpler, but the additional conjunction (with `[^]*`) made
956  // it noticeably slower. Concrete `a & 2` was twice slower than
957  // `a & a`.
958  auto res = make_fresh_automaton(aut);
959  require(exp.single(),
960  "conjunction: exponent must be single, ", exp);
961  require(exp.finite(),
962  "conjunction: exponent must be finite, ", exp);
963  unsigned n = exp.min;
964  if (n < 2)
965  {
966  // automatonset::universal().
967  auto s = res->new_state();
968  res->set_initial(s);
969  res->set_final(s);
970  for (auto l: res->context().labelset()->generators())
971  res->new_transition(s, s, l);
972  if (n == 1)
973  // Don't return aut: we need the accessible part. However,
974  // `copy_into(accessible(aut), res)` seems more costly than
975  // a plain conjunction!
976  res = strip(conjunction(res, aut));
977  }
978  else
979  {
980  res = strip(conjunction(aut, aut));
981  n -= 2;
982  static bool iterative = getenv("VCSN_ITERATIVE");
983  if (iterative)
984  for (size_t i = 0; i < n; ++i)
985  res = strip(conjunction(res, aut));
986  else
987  {
988  auto power = strip(aut);
989  while (true)
990  {
991  if (n % 2)
992  res = strip(conjunction(res, power));
993  n /= 2;
994  if (!n)
995  break;
996  power = strip(conjunction(power, power));
997  }
998  }
999  }
1000 
1001  return res;
1002  }
1003 
1004 
1005  namespace dyn
1006  {
1007  namespace detail
1008  {
1010  template <Automaton Aut, typename Unsigned>
1011  automaton
1012  conjunction_repeated(const automaton& aut, unsigned n)
1013  {
1014  const auto& a = aut->as<Aut>();
1016  }
1017  }
1018  }
1019 
1020  /*-----------------------------.
1021  | conjunction(value, value). |
1022  `-----------------------------*/
1023 
1025  template <typename ValueSet>
1026  typename ValueSet::value_t
1027  conjunction(const ValueSet& rs,
1028  const typename ValueSet::value_t& lhs,
1029  const typename ValueSet::value_t& rhs)
1030  {
1031  return rs.conjunction(lhs, rhs);
1032  }
1033 
1034  /*---------------------------------------.
1035  | conjunction(expression, expression). |
1036  `---------------------------------------*/
1037 
1038  namespace dyn
1039  {
1040  namespace detail
1041  {
1043  template <typename ExpSetLhs, typename ExpSetRhs>
1044  expression
1046  {
1047  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
1048  return {std::get<0>(join_elts),
1049  ::vcsn::conjunction(std::get<0>(join_elts),
1050  std::get<1>(join_elts),
1051  std::get<2>(join_elts))};
1052  }
1053  }
1054  }
1055 
1056  /*-------------------------------------.
1057  | conjunction(expansion, expansion). |
1058  `-------------------------------------*/
1059 
1060  namespace dyn
1061  {
1062  namespace detail
1063  {
1065  template <typename ExpSetLhs, typename ExpSetRhs>
1066  expansion
1068  {
1069  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
1070  return {std::get<0>(join_elts),
1071  ::vcsn::conjunction(std::get<0>(join_elts),
1072  std::get<1>(join_elts),
1073  std::get<2>(join_elts))};
1074  }
1075  }
1076  }
1077 
1078  /*---------------------------------------.
1079  | conjunction(polynomial, polynomial). |
1080  `---------------------------------------*/
1081 
1082  namespace dyn
1083  {
1084  namespace detail
1085  {
1087  template <typename PolynomialSetLhs, typename PolynomialSetRhs>
1088  polynomial
1090  {
1091  auto join_elts = join<PolynomialSetLhs, PolynomialSetRhs>(lhs, rhs);
1092  return {std::get<0>(join_elts),
1093  ::vcsn::conjunction(std::get<0>(join_elts),
1094  std::get<1>(join_elts),
1095  std::get<2>(join_elts))};
1096  }
1097  }
1098  }
1099 }
auto tuple(const Auts &...as)
Build the (accessible part of the) tuple.
typename tuple_automaton_impl::state_name_t state_name_t
auto is_proper_in(const state_name_t &sn) const -> std::enable_if_t< labelset_t_of< input_automaton_t< I >>::has_one(), bool >
Whether the state has only proper incoming transitions.
Definition: conjunction.hh:485
automaton infiltrate_(const std::vector< automaton > &as, vcsn::detail::index_sequence< I... >)
Variadic bridge helper.
Definition: conjunction.hh:888
typename weightset_t::value_t weight_t
Definition: conjunction.hh:81
auto labelset(Args &&...args) const -> decltype(aut_-> labelset(std::forward< Args >(args)...))
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
weight_t add_shuffle_transitions_(const state_t src, const state_name_t &psrc, seq< I... >)
Let all automata advance one after the other, and add the corresponding transitions in the output...
Definition: conjunction.hh:538
auto shuffle(const Auts &...as) -> tuple_automaton< decltype(join_automata(as...)), Auts... >
The (accessible part of the) shuffle product.
Definition: conjunction.hh:784
expression shuffle_expression(const expression &lhs, const expression &rhs)
Bridge (shuffle).
Definition: conjunction.hh:842
Decorator implementing the laziness for an algorithm.
auto conjunction_lazy(const Aut &a, const Auts &...as)
Build the (accessible part of the) conjunction, on-the-fly.
Definition: conjunction.hh:633
void infiltrate()
Compute the (accessible part of the) infiltration product.
Definition: conjunction.hh:205
expansion conjunction_expansion(const expansion &lhs, const expansion &rhs)
Bridge (conjunction).
static symbol sname_(const T &...t)
zipped_maps< Dereference, Maps... > zip_map_tuple(const std::tuple< Maps... > &maps)
Definition: zip-maps.hh:257
Definition: a-star.hh:8
bool is_proper(const Aut &aut)
Test whether an automaton is proper.
Definition: is-proper.hh:47
typename tuple_automaton_impl::state_t state_t
auto insplit(Aut aut, bool lazy=false) -> std::enable_if_t< labelset_t_of< Aut >::has_one(), decltype(make_insplit_automaton(aut))>
Insplit an automaton with possible spontaneous transitions.
Definition: insplit.hh:266
auto all_in(Args &&...args) const -> decltype(aut_-> all_in(std::forward< Args >(args)...))
weightset_mixin< detail::b_impl > b
Definition: fwd.hh:48
return res
Definition: multiply.hh:398
value_impl< detail::polynomial_tag > polynomial
Definition: fwd.hh:27
std::tuple< typename transition_map_t< Auts >::map_t &... > out_(const state_name_t &ss)
The outgoing tuple of transitions from state tuple ss.
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
constexpr auto is_proper_in(const state_name_t &) const -> std::enable_if_t<!labelset_t_of< input_automaton_t< I >>::has_one(), bool >
Whether the state has only proper incoming transitions.
Definition: conjunction.hh:472
if(exp.max==-1)
Definition: multiply.hh:381
An input/output format for valuesets.
Definition: format.hh:13
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: conjunction.hh:69
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:91
std::enable_if_t< labelset_t_of< Aut_ >::has_one(), bool > is_one(const Aut_ &aut, transition_t_of< Aut_ > tr) const
Check if the transition is spontaneous (in the case of a labelset with one).
Definition: conjunction.hh:455
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
bool has_proper_out(const state_name_t &psrc)
Whether the Ith state of psrc in the Ith input automaton has proper outgoing transitions (but possibl...
Definition: conjunction.hh:508
auto conjunction(const Aut &a, const Auts &...as)
Build the (accessible part of the) conjunction.
Definition: conjunction.hh:622
Tag to request the most appropriate version of an algorithm.
Definition: tags.hh:16
automaton conjunction_repeated(const automaton &aut, unsigned n)
Bridge (conjunction).
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
Aut automaton_t
The type of the resulting automaton.
Definition: conjunction.hh:45
expression infiltrate_expression(const expression &lhs, const expression &rhs)
Bridge (infiltrate).
Definition: conjunction.hh:927
void add_conjunction_transitions(const state_t src, const state_name_t &psrc)
Add transitions to the result automaton, starting from the given result input state, which must correspond to the given pair of input state automata.
Definition: conjunction.hh:290
const weightset_t & ws_
The resulting weightset.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
bool all(Bool &&...values)
Whether all the values evaluate as true.
Definition: tuple.hh:446
typename std::tuple_element< I, T >::type tuple_element_t
C++14.
Definition: tuple.hh:14
A static range.
Definition: tuple.hh:83
std::shared_ptr< detail::tuple_automaton_impl< Auts... >> tuple_automaton
A tuple automaton as a shared pointer.
typename labelset_t::value_t label_t
Definition: conjunction.hh:80
void add_one_transitions_(const state_t src, const state_name_t &psrc, seq< I... >)
Add the spontaneous transitions leaving state src, if it is relevant (i.e.
Definition: conjunction.hh:392
auto meet_automata(Auts &&...auts) -> decltype(pass(auts->null_state()...), make_mutable_automaton(meet(auts->context()...)))
An automaton whose type is the meet between those of auts.
bool are_proper_in(const state_name_t &psrc, seq< I... >) const
Whether no tapes in the sequence have spontaneous incoming transitions.
Definition: conjunction.hh:438
weight_t add_shuffle_transitions_(const state_t src, const state_name_t &psrc)
Let Ith automaton advance, and add the corresponding transitions in the output.
Definition: conjunction.hh:565
std::enable_if_t< sizeof...(Auts)==2 &&!L > ldivide_here()
Compute the left quotient in-place.
Definition: conjunction.hh:150
typename super_t::state_t state_t
Definition: conjunction.hh:51
automaton conjunction_(const std::vector< automaton > &as, bool lazy, vcsn::detail::index_sequence< I... >)
Bridge helper.
Definition: conjunction.hh:652
state_t state(Args &&...args)
Conversion from state name to state number.
automaton shuffle_(const std::vector< automaton > &as, vcsn::detail::index_sequence< I... >)
Variadic bridge helper.
Definition: conjunction.hh:802
std::enable_if_t<!LS::has_one(), void > add_one_transitions_(const LS &, const state_t, const state_name_t &)
In the case where the labelset doesn't have one, do nothing.
Definition: conjunction.hh:406
auto conjunction(const Aut &aut, to exp) -> fresh_automaton_t_of< Aut >
Repeated conjunction of a automaton.
Definition: conjunction.hh:951
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
std::shared_ptr< const node< Context >> expression
Definition: fwd.hh:187
base_t< tuple_element_t< I, automata_t >> input_automaton_t
The type of the Ith input automaton, unqualified.
Definition: conjunction.hh:88
void add_transitions(const state_t src, const state_name_t &psrc)
Tell lazy_tuple_automaton how to add the transitions to a state.
Definition: conjunction.hh:261
product_automaton_impl(Aut aut, const Auts &...auts)
Build a product automaton.
Definition: conjunction.hh:95
std::remove_cv_t< std::remove_reference_t< T >> base_t
T without reference or const/volatile qualifiers.
Definition: traits.hh:13
Request the Boolean specialization for determinization (B and F2).
Definition: tags.hh:132
std::shared_ptr< detail::product_automaton_impl< Lazy, Aut, Auts... >> product_automaton
A product automaton as a shared pointer.
Definition: conjunction.hh:603
auto make_product_automaton(Aut aut, const Auts &...auts) -> product_automaton< Lazy, Aut, Auts... >
Definition: conjunction.hh:607
A dyn automaton.
Definition: automaton.hh:17
typename super_t::template transition_map_t< A > transition_map_t
Definition: conjunction.hh:54
void cross_tuple(Fun f, const std::tuple< Ts... > &ts)
Definition: tuple.hh:301
std::tuple< transition_map_t< Auts >... > transition_maps_
Transition caches.
std::enable_if_t< sizeof...(Auts)==2 &&!L > ldivide()
Compute the left quotient.
Definition: conjunction.hh:115
std::enable_if_t< sizeof...(Auts)==2 &&!L > add()
Compute the deterministic sum of two deterministic automata.
Definition: conjunction.hh:131
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
typename super_t::template seq< I... > seq
Definition: conjunction.hh:57
STL namespace.
typename super_t::state_name_t state_name_t
Definition: conjunction.hh:50
Request for the weighted version of an algorithm.
Definition: tags.hh:149
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
bool have_proper_out(const state_name_t &psrc, seq< I... >)
Whether all the tapes in the sequence have proper outgoing transitions (but possibly spontaneous too)...
Definition: conjunction.hh:446
auto rs
Definition: lift.hh:152
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:165
auto infiltrate(const A1 &a1, const A2 &a2) -> tuple_automaton< decltype(join_automata(a1, a2)), A1, A2 >
The (accessible part of the) infiltration product.
Definition: conjunction.hh:861
std::tuple< Auts... > automata_t
The type of input automata.
Definition: conjunction.hh:84
value_impl< detail::expansion_tag > expansion
Definition: fwd.hh:24
An exponent, or range of exponents.
Definition: to.hh:25
std::enable_if_t< sizeof...(Auts)==2 &&!L > add_ldivide_transitions(const state_t src, const state_name_t &psrc)
Behave similarly to add_conjunction_transitions, with three main differences: the algorithm continues...
Definition: conjunction.hh:319
A dyn Value/ValueSet.
Definition: fwd.hh:23
std::enable_if_t< LS::has_one(), void > add_one_transitions_(const LS &ls, const state_t src, const state_name_t &psrc)
If the I-th labelset has one, add the relevant spontaneous transitions leaving the state...
Definition: conjunction.hh:413
weightset_t_of< context_t > weightset_t
Definition: conjunction.hh:78
auto join_automata(Auts &&...auts) -> decltype(pass(auts->null_state()...), make_mutable_automaton(join(auts->context()...)))
An automaton whose type is the join between those of auts.
expression conjunction_expression(const expression &lhs, const expression &rhs)
Bridge (conjunction).
polynomial conjunction_polynomial(const polynomial &lhs, const polynomial &rhs)
Bridge (conjunction).
auto add_transition(Args &&...args) -> decltype(aut_-> add_transition(std::forward< Args >(args)...))
std::enable_if_t< sizeof...(Auts)==2 &&!L > add_add_transitions(const state_t src, const state_name_t &psrc)
Behaves similarly to add_conjunction_transitions on a Boolean weightset, but use post() as a special ...
Definition: conjunction.hh:359
automaton_t aut_
The wrapped automaton, possibly const.
#define Automaton
Definition: automaton.hh:23
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
ValueSet::value_t conjunction(const ValueSet &rs, const typename ValueSet::value_t &lhs, const typename ValueSet::value_t &rhs)
Intersection/Hadamard product of expressions/polynomials.
void shuffle()
Compute the (accessible part of the) shuffle product.
Definition: conjunction.hh:179
context_t_of< Aut > context_t
The context of the result.
Definition: conjunction.hh:76
constexpr std::enable_if_t<!labelset_t_of< Aut_ >::has_one(), bool > is_one(const Aut_ &, transition_t_of< Aut_ >) const
Same as above, but for labelsets without one, so it's always false.
Definition: conjunction.hh:464
void initialize_shuffle()
Fill the worklist with the initial source-state pairs, as needed for the shuffle algorithm.
Definition: conjunction.hh:277
auto rdivide(const Aut1 &a1, const Aut2 &a2)
Compute the right quotient.
Definition: conjunction.hh:753
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
void add_shuffle_transitions(const state_t src, const state_name_t &psrc)
Add transitions to the given result automaton, starting from the given result input state...
Definition: conjunction.hh:525
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
auto lweight(Args &&...args) -> decltype(aut_-> lweight(std::forward< Args >(args)...))
void conjunction()
Compute the (accessible part of the) conjunction.
Definition: conjunction.hh:100
Build the (accessible part of the) product.
Definition: conjunction.hh:37
void initialize_conjunction()
Fill the worklist with the initial source-state pairs, as needed for the conjunction algorithm...
Definition: conjunction.hh:270
auto all_out(state_t s) const -> decltype(all_out(aut_, s))
All the outgoing transitions.
labelset_t_of< context_t > labelset_t
Definition: conjunction.hh:77
auto new_transition(Args &&...args) -> decltype(aut_-> new_transition(std::forward< Args >(args)...))
product_automaton_impl self_t
Definition: conjunction.hh:46
constexpr bool all_()
Definition: tuple.hh:439
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46