Vcsn  2.3
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 = insplit(rhs);
704  auto prod =
705  detail::make_product_automaton<false>(join_automata(lhs, res), lhs, res);
706  prod->ldivide_here();
707  return res;
708  }
709 
710  template <Automaton Aut1, Automaton Aut2>
711  auto
712  ldivide(const Aut1& lhs, const Aut2& rhs, weighted_tag)
713  {
714  auto prod =
715  detail::make_product_automaton<false>(join_automata(lhs, rhs), lhs, rhs);
716  prod->ldivide();
717  return prod->strip();
718  }
719 
720 
721  namespace dyn
722  {
723  namespace detail
724  {
726  template <Automaton Aut1, Automaton Aut2>
727  automaton
728  ldivide(const automaton& aut1, const automaton& aut2)
729  {
730  const auto& a1 = aut1->as<Aut1>();
731  const auto& a2 = aut2->as<Aut2>();
732  return vcsn::ldivide<Aut1, Aut2>(a1, a2);
733  }
734  }
735  }
736 
737 
738 
739  /*---------------------------------.
740  | rdivide(automaton, automaton). |
741  `---------------------------------*/
742 
747  template <Automaton Aut1, Automaton Aut2>
748  auto
749  rdivide(const Aut1& a1, const Aut2& a2)
750  {
751  auto a1t = transpose(a1);
752  auto a2t = transpose(a2);
753  return transpose(ldivide(a2t, a1t));
754  }
755 
756  namespace dyn
757  {
758  namespace detail
759  {
761  template <Automaton Aut1, Automaton Aut2>
762  automaton
763  rdivide(const automaton& aut1, const automaton& aut2)
764  {
765  const auto& a1 = aut1->as<Aut1>();
766  const auto& a2 = aut2->as<Aut2>();
767  return vcsn::rdivide(a1, a2);
768  }
769  }
770  }
771 
772 
773  /*------------------------.
774  | shuffle(automaton...). |
775  `------------------------*/
776 
778  template <Automaton... Auts>
779  auto
780  shuffle(const Auts&... as)
781  // SFINAE
782  -> tuple_automaton<decltype(join_automata(as...)),
783  Auts...>
784  {
785  auto res =
786  detail::make_product_automaton<false>(join_automata(as...), as...);
787  res->shuffle();
788  return res->strip();
789  }
790 
791  namespace dyn
792  {
793  namespace detail
794  {
796  template <typename Auts, size_t... I>
797  automaton
798  shuffle_(const std::vector<automaton>& as,
800  {
801  return vcsn::shuffle(as[I]->as<tuple_element_t<I, Auts>>()...);
802  }
803 
805  template <typename Auts>
806  automaton
807  shuffle(const std::vector<automaton>& as)
808  {
809  auto indices
811  return shuffle_<Auts>(as, indices);
812  }
813  }
814  }
815 
816 
817  /*-----------------------------------.
818  | shuffle(expression, expression). |
819  `-----------------------------------*/
820 
822  template <typename ValueSet>
823  typename ValueSet::value_t
824  shuffle(const ValueSet& vs,
825  const typename ValueSet::value_t& lhs,
826  const typename ValueSet::value_t& rhs)
827  {
828  return vs.shuffle(lhs, rhs);
829  }
830 
831  namespace dyn
832  {
833  namespace detail
834  {
836  template <typename ExpSetLhs, typename ExpSetRhs>
837  expression
838  shuffle_expression(const expression& lhs, const expression& rhs)
839  {
840  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
841  return {std::get<0>(join_elts),
842  ::vcsn::shuffle(std::get<0>(join_elts),
843  std::get<1>(join_elts),
844  std::get<2>(join_elts))};
845  }
846  }
847  }
848 
849 
850  /*----------------------------.
851  | infiltrate(automaton...). |
852  `----------------------------*/
853 
855  template <Automaton A1, Automaton A2>
856  auto
857  infiltrate(const A1& a1, const A2& a2)
858  -> tuple_automaton<decltype(join_automata(a1, a2)),
859  A1, A2>
860  {
861  auto res =
862  detail::make_product_automaton<false>(join_automata(a1, a2), a1, a2);
863  res->infiltrate();
864  return res->strip();
865  }
866 
868  template <Automaton A1, Automaton A2, Automaton A3, Automaton... Auts>
869  auto
870  infiltrate(const A1& a1, const A2& a2, const A3& a3, const Auts&... as)
871  // SFINAE
872  -> decltype(infiltrate(infiltrate(a1, a2), a3, as...))
873  {
874  return infiltrate(infiltrate(a1, a2), a3, as...);
875  }
876 
877  namespace dyn
878  {
879  namespace detail
880  {
882  template <typename Auts, size_t... I>
883  automaton
884  infiltrate_(const std::vector<automaton>& as,
886  {
887  return vcsn::infiltrate(as[I]->as<tuple_element_t<I, Auts>>()...);
888  }
889 
891  template <typename Auts>
892  automaton
893  infiltrate(const std::vector<automaton>& as)
894  {
895  auto indices
897  return infiltrate_<Auts>(as, indices);
898  }
899  }
900  }
901 
902  /*--------------------------------------.
903  | infiltrate(expression, expression). |
904  `--------------------------------------*/
905 
907  template <typename ValueSet>
908  typename ValueSet::value_t
909  infiltrate(const ValueSet& vs,
910  const typename ValueSet::value_t& lhs,
911  const typename ValueSet::value_t& rhs)
912  {
913  return vs.infiltrate(lhs, rhs);
914  }
915 
916  namespace dyn
917  {
918  namespace detail
919  {
921  template <typename ExpSetLhs, typename ExpSetRhs>
922  expression
924  {
925  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
926  return {std::get<0>(join_elts),
927  ::vcsn::infiltrate(std::get<0>(join_elts),
928  std::get<1>(join_elts),
929  std::get<2>(join_elts))};
930  }
931  }
932  }
933 
934 
935  /*-----------------------------.
936  | conjunction(automaton, n). |
937  `-----------------------------*/
938 
945  template <Automaton Aut>
946  auto
947  conjunction(const Aut& aut, to exp)
949  {
950  // We used to compute `a & n` as `([^]* & a) & a)...`. The code
951  // was simpler, but the additional conjunction (with `[^]*`) made
952  // it noticeably slower. Concrete `a & 2` was twice slower than
953  // `a & a`.
954  auto res = make_fresh_automaton(aut);
955  require(exp.single(),
956  "conjunction: exponent must be single, ", exp);
957  require(exp.finite(),
958  "conjunction: exponent must be finite, ", exp);
959  unsigned n = exp.min;
960  if (n < 2)
961  {
962  // automatonset::universal().
963  auto s = res->new_state();
964  res->set_initial(s);
965  res->set_final(s);
966  for (auto l: res->context().labelset()->generators())
967  res->new_transition(s, s, l);
968  if (n == 1)
969  // Don't return aut: we need the accessible part. However,
970  // `copy_into(accessible(aut), res)` seems more costly than
971  // a plain conjunction!
972  res = strip(conjunction(res, aut));
973  }
974  else
975  {
976  res = strip(conjunction(aut, aut));
977  n -= 2;
978  static bool iterative = getenv("VCSN_ITERATIVE");
979  if (iterative)
980  for (size_t i = 0; i < n; ++i)
981  res = strip(conjunction(res, aut));
982  else
983  {
984  auto power = strip(aut);
985  while (true)
986  {
987  if (n % 2)
988  res = strip(conjunction(res, power));
989  n /= 2;
990  if (!n)
991  break;
992  power = strip(conjunction(power, power));
993  }
994  }
995  }
996 
997  return res;
998  }
999 
1000 
1001  namespace dyn
1002  {
1003  namespace detail
1004  {
1006  template <Automaton Aut, typename Unsigned>
1007  automaton
1008  conjunction_repeated(const automaton& aut, unsigned n)
1009  {
1010  const auto& a = aut->as<Aut>();
1012  }
1013  }
1014  }
1015 
1016  /*-----------------------------.
1017  | conjunction(value, value). |
1018  `-----------------------------*/
1019 
1021  template <typename ValueSet>
1022  typename ValueSet::value_t
1023  conjunction(const ValueSet& rs,
1024  const typename ValueSet::value_t& lhs,
1025  const typename ValueSet::value_t& rhs)
1026  {
1027  return rs.conjunction(lhs, rhs);
1028  }
1029 
1030  /*---------------------------------------.
1031  | conjunction(expression, expression). |
1032  `---------------------------------------*/
1033 
1034  namespace dyn
1035  {
1036  namespace detail
1037  {
1039  template <typename ExpSetLhs, typename ExpSetRhs>
1040  expression
1042  {
1043  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
1044  return {std::get<0>(join_elts),
1045  ::vcsn::conjunction(std::get<0>(join_elts),
1046  std::get<1>(join_elts),
1047  std::get<2>(join_elts))};
1048  }
1049  }
1050  }
1051 
1052  /*-------------------------------------.
1053  | conjunction(expansion, expansion). |
1054  `-------------------------------------*/
1055 
1056  namespace dyn
1057  {
1058  namespace detail
1059  {
1061  template <typename ExpSetLhs, typename ExpSetRhs>
1062  expansion
1064  {
1065  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
1066  return {std::get<0>(join_elts),
1067  ::vcsn::conjunction(std::get<0>(join_elts),
1068  std::get<1>(join_elts),
1069  std::get<2>(join_elts))};
1070  }
1071  }
1072  }
1073 
1074  /*---------------------------------------.
1075  | conjunction(polynomial, polynomial). |
1076  `---------------------------------------*/
1077 
1078  namespace dyn
1079  {
1080  namespace detail
1081  {
1083  template <typename PolynomialSetLhs, typename PolynomialSetRhs>
1084  polynomial
1086  {
1087  auto join_elts = join<PolynomialSetLhs, PolynomialSetRhs>(lhs, rhs);
1088  return {std::get<0>(join_elts),
1089  ::vcsn::conjunction(std::get<0>(join_elts),
1090  std::get<1>(join_elts),
1091  std::get<2>(join_elts))};
1092  }
1093  }
1094  }
1095 }
void conjunction()
Compute the (accessible part of the) conjunction.
Definition: conjunction.hh:100
polynomial conjunction_polynomial(const polynomial &lhs, const polynomial &rhs)
Bridge (conjunction).
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.
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
auto labelset(Args &&...args) const -> decltype(aut_-> labelset(std::forward< Args >(args)...))
product_automaton_impl self_t
Definition: conjunction.hh:46
base_t< tuple_element_t< I, automata_t >> input_automaton_t
The type of the Ith input automaton, unqualified.
Definition: conjunction.hh:88
auto conjunction_lazy(const Aut &a, const Auts &...as)
Build the (accessible part of the) conjunction, on-the-fly.
Definition: conjunction.hh:633
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: conjunction.hh:69
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:238
typename std::tuple_element< I, T >::type tuple_element_t
C++14.
Definition: tuple.hh:14
#define Automaton
Definition: automaton.hh:23
std::shared_ptr< detail::tuple_automaton_impl< Auts... >> tuple_automaton
A tuple automaton as a shared pointer.
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
std::shared_ptr< const node< Context >> expression
Definition: fwd.hh:187
std::tuple< transition_map_t< Auts >... > transition_maps_
Transition caches.
STL namespace.
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
auto all_in(Args &&...args) const -> decltype(aut_-> all_in(std::forward< Args >(args)...))
std::shared_ptr< detail::product_automaton_impl< Lazy, Aut, Auts... >> product_automaton
A product automaton as a shared pointer.
Definition: conjunction.hh:603
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
static symbol sname_(const T &...t)
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
typename super_t::state_name_t state_name_t
Definition: conjunction.hh:50
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
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
constexpr bool all_()
Definition: tuple.hh:439
typename tuple_automaton_impl::state_name_t state_name_t
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
auto conjunction(const Aut &a, const Auts &...as)
Build the (accessible part of the) conjunction.
Definition: conjunction.hh:622
expansion conjunction_expansion(const expansion &lhs, const expansion &rhs)
Bridge (conjunction).
std::enable_if_t< sizeof...(Auts)==2 &&!L > ldivide()
Compute the left quotient.
Definition: conjunction.hh:115
Tag to request the most appropriate version of an algorithm.
Definition: tags.hh:16
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
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.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
A static range.
Definition: tuple.hh:83
Build the (accessible part of the) product.
Definition: conjunction.hh:37
auto make_product_automaton(Aut aut, const Auts &...auts) -> product_automaton< Lazy, Aut, Auts... >
Definition: conjunction.hh:607
typename weightset_t::value_t weight_t
Definition: conjunction.hh:81
typename super_t::template seq< I... > seq
Definition: conjunction.hh:57
A dyn Value/ValueSet.
Definition: fwd.hh:23
void shuffle()
Compute the (accessible part of the) shuffle product.
Definition: conjunction.hh:179
typename super_t::template transition_map_t< A > transition_map_t
Definition: conjunction.hh:54
return res
Definition: multiply.hh:398
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
std::enable_if_t< sizeof...(Auts)==2 &&!L > add()
Compute the deterministic sum of two deterministic automata.
Definition: conjunction.hh:131
auto tuple(const Auts &...as)
Build the (accessible part of the) tuple.
void infiltrate()
Compute the (accessible part of the) infiltration product.
Definition: conjunction.hh:205
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
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
typename tuple_automaton_impl::state_t state_t
weightset_t_of< context_t > weightset_t
Definition: conjunction.hh:78
auto shuffle(const Auts &...as) -> tuple_automaton< decltype(join_automata(as...)), Auts... >
The (accessible part of the) shuffle product.
Definition: conjunction.hh:780
const weightset_t & ws_
The resulting weightset.
auto rs
Definition: lift.hh:152
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:91
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
Definition: a-star.hh:8
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 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
Request the Boolean specialization for determinization (B and F2).
Definition: tags.hh:123
automaton conjunction_(const std::vector< automaton > &as, bool lazy, vcsn::detail::index_sequence< I... >)
Bridge helper.
Definition: conjunction.hh:652
expression shuffle_expression(const expression &lhs, const expression &rhs)
Bridge (shuffle).
Definition: conjunction.hh:838
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
automaton shuffle_(const std::vector< automaton > &as, vcsn::detail::index_sequence< I... >)
Variadic bridge helper.
Definition: conjunction.hh:798
void initialize_shuffle()
Fill the worklist with the initial source-state pairs, as needed for the shuffle algorithm.
Definition: conjunction.hh:277
An input/output format for valuesets.
Definition: format.hh:13
value_impl< detail::polynomial_tag > polynomial
Definition: fwd.hh:27
auto rdivide(const Aut1 &a1, const Aut2 &a2)
Compute the right quotient.
Definition: conjunction.hh:749
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:857
Request for the weighted version of an algorithm.
Definition: tags.hh:140
expression conjunction_expression(const expression &lhs, const expression &rhs)
Bridge (conjunction).
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 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.
auto all_out(state_t s) const -> decltype(all_out(aut_, s))
All the outgoing transitions.
automaton infiltrate_(const std::vector< automaton > &as, vcsn::detail::index_sequence< I... >)
Variadic bridge helper.
Definition: conjunction.hh:884
value_impl< detail::expansion_tag > expansion
Definition: fwd.hh:24
std::enable_if_t< sizeof...(Auts)==2 &&!L > ldivide_here()
Compute the left quotient in-place.
Definition: conjunction.hh:150
std::remove_cv_t< std::remove_reference_t< T >> base_t
T without reference or const/volatile qualifiers.
Definition: traits.hh:13
bool all(Bool &&...values)
Whether all the values evaluate as true.
Definition: tuple.hh:446
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
std::tuple< Auts... > automata_t
The type of input automata.
Definition: conjunction.hh:84
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
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.
bool is_proper(const Aut &aut)
Test whether an automaton is proper.
Definition: is-proper.hh:47
auto conjunction(const Aut &aut, to exp) -> fresh_automaton_t_of< Aut >
Repeated conjunction of a automaton.
Definition: conjunction.hh:947
void initialize_conjunction()
Fill the worklist with the initial source-state pairs, as needed for the conjunction algorithm...
Definition: conjunction.hh:270
product_automaton_impl(Aut aut, const Auts &...auts)
Build a product automaton.
Definition: conjunction.hh:95
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:145
typename super_t::state_t state_t
Definition: conjunction.hh:51
state_t state(Args &&...args)
Conversion from state name to state number.
zipped_maps< Dereference, Maps... > zip_map_tuple(const std::tuple< Maps... > &maps)
Definition: zip-maps.hh:257
automaton conjunction_repeated(const automaton &aut, unsigned n)
Bridge (conjunction).
auto add_transition(Args &&...args) -> decltype(aut_-> add_transition(std::forward< Args >(args)...))
void cross_tuple(Fun f, const std::tuple< Ts... > &ts)
Definition: tuple.hh:301
weightset_mixin< detail::b_impl > b
Definition: fwd.hh:48
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
automaton_t aut_
The wrapped automaton, possibly const.
context_t_of< Aut > context_t
The context of the result.
Definition: conjunction.hh:76
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
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
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 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
An exponent, or range of exponents.
Definition: to.hh:26
Decorator implementing the laziness for an algorithm.
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename labelset_t::value_t label_t
Definition: conjunction.hh:80
labelset_t_of< context_t > labelset_t
Definition: conjunction.hh:77
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
auto lweight(Args &&...args) -> decltype(aut_-> lweight(std::forward< Args >(args)...))
expression infiltrate_expression(const expression &lhs, const expression &rhs)
Bridge (infiltrate).
Definition: conjunction.hh:923
auto new_transition(Args &&...args) -> decltype(aut_-> new_transition(std::forward< Args >(args)...))
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
if(exp.max==-1)
Definition: multiply.hh:381