Vcsn  2.2
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/insplit.hh>
8 #include <vcsn/algos/strip.hh>
13 #include <vcsn/ctx/context.hh>
14 #include <vcsn/ctx/traits.hh>
15 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
16 #include <vcsn/dyn/expression.hh> // dyn::make_expression
17 #include <vcsn/dyn/polynomial.hh>
18 #include <vcsn/misc/tuple.hh> // tuple_element_t, cross_tuple
19 #include <vcsn/misc/zip-maps.hh>
20 
21 namespace vcsn
22 {
23  namespace detail
24  {
25  /*---------------------------------.
26  | product_automaton_impl<Aut...>. |
27  `---------------------------------*/
28 
30  template <bool Lazy, Automaton Aut, Automaton... Auts>
32  : public lazy_tuple_automaton<product_automaton_impl<Lazy, Aut, Auts...>, false, Lazy, Aut, Auts...>
33  {
34  static_assert(all_<labelset_t_of<Auts>::is_letterized()...>(),
35  "product: requires letterized labels");
36 
38  using automaton_t = Aut;
41  using super_t = lazy_tuple_automaton<self_t, false, Lazy, Aut, Auts...>;
42 
43  public:
45  using state_t = typename super_t::state_t;
46 
47  template <Automaton A>
48  using transition_map_t = typename super_t::template transition_map_t<A>;
49 
50  template <size_t... I>
51  using seq
52  = typename tuple_automaton_t::element_type::template seq<I...>;
53 
54  using super_t::ws_;
56 
57  static symbol sname()
58  {
59  static symbol res("product_automaton"
60  + super_t::sname_(std::string{Lazy ? "true" : "false"}));
61  return res;
62  }
63 
64  std::ostream& print_set(std::ostream& o, format fmt = {}) const
65  {
66  o << "product_automaton";
67  return aut_->print_set_(o, fmt);
68  }
69 
74 
75  using label_t = typename labelset_t::value_t;
76  using weight_t = typename weightset_t::value_t;
77 
79  using automata_t = std::tuple<Auts...>;
80 
82  template <size_t I>
84 
85  using super_t::aut_;
86 
90  product_automaton_impl(Aut aut, const Auts&... auts)
91  : super_t{aut, auts...}
92  {}
93 
95  void conjunction()
96  {
98 
99  if (!Lazy)
100  while (!aut_->todo_.empty())
101  {
102  const auto& p = aut_->todo_.front();
103  this->complete_(std::get<1>(p));
104  aut_->todo_.pop_front();
105  }
106  }
107 
109  void shuffle()
110  {
112 
113  while (!aut_->todo_.empty())
114  {
115  const auto& p = aut_->todo_.front();
116  add_shuffle_transitions<false>(std::get<1>(p), std::get<0>(p));
117  aut_->todo_.pop_front();
118  }
119  }
120 
123  {
124  // Variadic infiltration is not trivial to implement, it's not
125  // just conjunction and shuffle in series. For instance, consider
126  // three automata:
127  //
128  // <x>a
129  // x = -> 0 ------> 1 ->
130  //
131  // and likewise for y and z. Let's use `&:` to denote
132  // infiltration. In (x &: y) there is a transition ((0,0),
133  // <xy>a, (1,1)) coming from the conjunction-like transitions.
134  //
135  // Therefore in (x &: y) &: z there is a transition ((0,0),0),
136  // <xy>a, (1,1), 0) by virtue of the shuffle-like transitions.
137  //
138  // This kind of transition that mixes conjunction and shuffle
139  // would never appear in a naive implementation with only
140  // conjunction and shuffle transitions, but no combinations.
141  require(sizeof...(Auts) == 2,
142  "infiltration: variadic product does not work");
143 
144  // Infiltrate is a mix of conjunction and shuffle operations, and
145  // the initial states for shuffle are a superset of the
146  // initial states for conjunction:
148 
149  while (!aut_->todo_.empty())
150  {
151  const auto& p = aut_->todo_.front();
152  // Infiltrate is a mix of conjunction and shuffle operations.
153  //
154  // Conjunction transitions must be added before shuffle ones:
155  // this way "conjunction" can use "new_transition" only, which
156  // is faster than "add_transition".
157  add_conjunction_transitions(std::get<1>(p), std::get<0>(p));
158  add_shuffle_transitions<true>(std::get<1>(p), std::get<0>(p));
159 
160  aut_->todo_.pop_front();
161  }
162  }
163 
165  void add_transitions(const state_t src,
166  const state_name_t& psrc)
167  {
168  add_conjunction_transitions(src, psrc);
169  }
170 
171  private:
175  {
176  aut_->todo_.emplace_back(aut_->pre_(), aut_->pre());
177  }
178 
182  {
183  // Make the result automaton initial states: same as the
184  // conjunction of pre: synchronized transitions on $.
185  add_conjunction_transitions(aut_->pre(), aut_->pre_());
186  }
187 
188 
189  using super_t::out_;
190  using super_t::state;
196  const state_name_t& psrc)
197  {
198  for (auto t: zip_map_tuple(out_(psrc)))
199  // These are always new transitions: first because the
200  // source state is visited for the first time, and second
201  // because the couple (left destination, label) is unique,
202  // and so is (right destination, label).
203  if (!aut_->labelset()->is_one(t.first))
205  ([this,src,&t]
206  (const typename transition_map_t<Auts>::transition&... ts)
207  {
208  this->new_transition(src, state(ts.dst...),
209  t.first,
210  ws_.mul(ts.weight()...));
211  },
212  t.second);
213  add_one_transitions_(src, psrc, aut_->indices);
214  }
215 
218  template <std::size_t... I>
219  void
220  add_one_transitions_(const state_t src, const state_name_t& psrc,
221  seq<I...>)
222  {
223  using swallow = int[];
224  (void) swallow
225  {
226  (maybe_add_one_transitions_<I>(*(std::get<I>(aut_->auts_)->labelset()),
227  src, psrc), 0)...
228  };
229  }
230 
232  template <std::size_t I, typename L>
233  std::enable_if_t<!L::has_one(), void>
235  {}
236 
239  template <std::size_t I, typename L>
240  std::enable_if_t<L::has_one(), void>
241  maybe_add_one_transitions_(const L& ls, const state_t src,
242  const state_name_t& psrc)
243  {
244  if (!has_one_in(psrc, I + 1, aut_->indices)
245  && !has_only_one_out(psrc, I, aut_->indices))
246  {
247  // one is guaranteed to be first.
248  const auto& tmap = std::get<I>(transition_maps_)[std::get<I>(psrc)];
249  if (!tmap.empty() && ls.is_one(tmap.begin()->first))
250  for (auto t : tmap.begin()->second)
251  {
252  auto pdst = psrc;
253  std::get<I>(pdst) = t.dst;
254  this->new_transition(src, state(pdst), ls.one(), t.weight());
255  }
256  }
257  }
258 
261  template <std::size_t... I>
262  bool has_one_in(const state_name_t& psrc, std::size_t i,
263  seq<I...>) const
264  {
265  bool has_ones[] = { is_spontaneous_in(std::get<I>(aut_->auts_),
266  std::get<I>(psrc))... };
267  for (; i < sizeof...(Auts); ++i)
268  if (has_ones[i])
269  return true;
270  return false;
271  }
272 
275  template <std::size_t... I>
276  bool has_only_one_out(const state_name_t& psrc, std::size_t i,
277  seq<I...>)
278  {
279  bool has_ones[] = { has_only_ones_out<I>(psrc)... };
280  for (size_t j = 0; j < i; ++j)
281  if (has_ones[j])
282  return true;
283  return false;
284  }
285 
288  template <Automaton Aut_>
289  std::enable_if_t<labelset_t_of<Aut_>::has_one(), bool>
290  is_one(const Aut_& aut, transition_t_of<Aut_> tr) const
291  {
292  return aut->labelset()->is_one(aut->label_of(tr));
293  }
294 
297  template <Automaton Aut_>
298  constexpr std::enable_if_t<!labelset_t_of<Aut_>::has_one(), bool>
299  is_one(const Aut_&, transition_t_of<Aut_>) const
300  {
301  return false;
302  }
303 
307  template <Automaton Aut_>
308  constexpr std::enable_if_t<!labelset_t_of<Aut_>::has_one(), bool>
309  is_spontaneous_in(const Aut_&,
310  state_t_of<Aut_>) const
311  {
312  return false;
313  }
314 
319  template <Automaton Aut_>
320  std::enable_if_t<labelset_t_of<Aut_>::has_one(), bool>
321  is_spontaneous_in(const Aut_& rhs, state_t_of<Aut_> rst) const
322  {
323  auto rin = all_in(rhs, rst);
324  auto rtr = rin.begin();
325  return rtr != rin.end() && is_one(rhs, *rtr);
326  }
327 
330  template <size_t I>
331  bool
333  {
334  const auto& tmap = std::get<I>(transition_maps_)[std::get<I>(psrc)];
335  auto s = tmap.size();
336  if (s == 0)
337  return true;
338  else if (2 <= s)
339  return false;
340  else
341  return std::get<I>(aut_->auts_)->labelset()->is_one(tmap.begin()->first);
342  }
343 
348  template <bool Infiltration = false>
350  const state_name_t& psrc)
351  {
352  weight_t final
353  = add_shuffle_transitions_<Infiltration>(src, psrc, aut_->indices);
354  aut_->set_final(src, final);
355  }
356 
361  template <bool Infiltration, size_t... I>
363  const state_name_t& psrc,
364  seq<I...>)
365  {
366  weight_t res = ws_.one();
367  using swallow = int[];
368  (void) swallow
369  {
370  (res = ws_.mul(res,
371  add_shuffle_transitions_<Infiltration, I>(src, psrc)),
372  0)...
373  };
374  return res;
375  }
376 
387  template <bool Infiltration, size_t I>
388  weight_t
390  const state_name_t& psrc)
391  {
392  // Whether is a final state.
393  weight_t res = ws_.zero();
394 
395  auto& ts = std::get<I>(transition_maps_)[std::get<I>(psrc)];
396  for (auto t: ts)
397  if (std::get<I>(aut_->auts_)->labelset()->is_special(t.first))
398  res = t.second.front().weight();
399  else
400  // The src state is visited for the first time, so all
401  // these transitions are new. *Except* in the case where
402  // we have a loop on some tapes.
403  //
404  // If add_conjunction_transitions was called before (in the
405  // case of infiltration), there may even exist such a
406  // transition in the first loop.
407  //
408  // To trigger the later case, try the self-infiltration on
409  // derived_term('a*a').
410  for (auto d: t.second)
411  {
412  auto pdst = psrc;
413  std::get<I>(pdst) = d.dst;
414  if (Infiltration
415  || std::get<I>(psrc) == d.dst)
416  this->add_transition(src, state(pdst), t.first, d.weight());
417  else
418  this->new_transition(src, state(pdst), t.first, d.weight());
419  }
420  return res;
421  }
422  };
423  }
424 
426  template <bool Lazy, Automaton Aut, Automaton... Auts>
427  using product_automaton
428  = std::shared_ptr<detail::product_automaton_impl<Lazy, Aut, Auts...>>;
429 
430  template <bool Lazy, Automaton Aut, Automaton... Auts>
431  inline
432  auto
433  make_product_automaton(Aut aut, const Auts&... auts)
434  -> product_automaton<Lazy, Aut, Auts...>
435  {
436  using res_t = product_automaton<Lazy, Aut, Auts...>;
437  return make_shared_ptr<res_t>(aut, auts...);
438  }
439 
440 
441  /*-----------------------------.
442  | conjunction(automaton...). |
443  `-----------------------------*/
444 
446  template <Automaton... Auts>
447  auto
448  conjunction(const Auts&... as)
449  -> tuple_automaton<decltype(meet_automata(as...)),
450  Auts...>
451  {
452  auto res = make_product_automaton<false>(meet_automata(as...),
453  as...);
454  res->conjunction();
455  return res->strip();
456  }
457 
459  template <Automaton... Auts>
460  auto
461  conjunction_lazy(const Auts&... as)
462  -> product_automaton<true, decltype(meet_automata(as...)),
463  Auts...>
464  {
465  auto res = make_product_automaton<true>(meet_automata(as...),
466  as...);
467  res->conjunction();
468  return res;
469  }
470 
471  namespace dyn
472  {
473  namespace detail
474  {
475  template <std::size_t I, Automaton Aut>
476  auto
477  do_insplit(Aut& aut)
478  -> std::enable_if_t<labelset_t_of<Aut>::has_one() && I != 0,
479  decltype(insplit(aut))>
480  {
481  return insplit(aut);
482  }
483 
484  template <std::size_t I, Automaton Aut>
485  std::enable_if_t<!labelset_t_of<Aut>::has_one() || I == 0, Aut&>
486  do_insplit(Aut& aut)
487  {
488  return aut;
489  }
490 
492  template <typename Auts, size_t... I>
493  automaton
494  conjunction_(const std::vector<automaton>& as, bool lazy,
496  {
497  if (lazy)
498  return make_automaton
500  (do_insplit<I>(as[I]->as<tuple_element_t<I, Auts>>())...));
501  else
502  return make_automaton
504  (do_insplit<I>(as[I]->as<tuple_element_t<I, Auts>>())...));
505  }
506 
508  template <typename Auts, typename Bool>
509  automaton
510  conjunction(const std::vector<automaton>& as, bool lazy)
511  {
512  auto indices
514  return conjunction_<Auts>(as, lazy, indices);
515  }
516  }
517  }
518 
519 
520  /*------------------------.
521  | shuffle(automaton...). |
522  `------------------------*/
523 
525  template <Automaton... Auts>
526  auto
527  shuffle(const Auts&... as)
528  -> tuple_automaton<decltype(join_automata(as...)),
529  Auts...>
530  {
531  auto res = make_product_automaton<false>(join_automata(as...), as...);
532  res->shuffle();
533  return res->strip();
534  }
535 
536  namespace dyn
537  {
538  namespace detail
539  {
541  template <typename Auts, size_t... I>
542  automaton
543  shuffle_(const std::vector<automaton>& as,
545  {
546  auto res = vcsn::shuffle(as[I]->as<tuple_element_t<I, Auts>>()...);
547  return make_automaton(res);
548  }
549 
551  template <typename Auts>
552  automaton
553  shuffle(const std::vector<automaton>& as)
554  {
555  auto indices
557  return shuffle_<Auts>(as, indices);
558  }
559  }
560  }
561 
562 
563  /*-----------------------------------.
564  | shuffle(expression, expression). |
565  `-----------------------------------*/
566 
568  template <typename ValueSet>
569  typename ValueSet::value_t
570  shuffle(const ValueSet& vs,
571  const typename ValueSet::value_t& lhs,
572  const typename ValueSet::value_t& rhs)
573  {
574  return vs.shuffle(lhs, rhs);
575  }
576 
577  namespace dyn
578  {
579  namespace detail
580  {
582  template <typename ExpSetLhs, typename ExpSetRhs>
583  expression
584  shuffle_expression(const expression& lhs, const expression& rhs)
585  {
586  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
587  return make_expression(std::get<0>(join_elts),
588  ::vcsn::shuffle(std::get<0>(join_elts),
589  std::get<1>(join_elts),
590  std::get<2>(join_elts)));
591  }
592  }
593  }
594 
595 
596  /*-----------------------------.
597  | infiltration(automaton...). |
598  `-----------------------------*/
599 
601  template <Automaton A1, Automaton A2>
602  auto
603  infiltration(const A1& a1, const A2& a2)
604  -> tuple_automaton<decltype(join_automata(a1, a2)),
605  A1, A2>
606  {
607  auto res = make_product_automaton<false>(join_automata(a1, a2), a1, a2);
608  res->infiltration();
609  return res->strip();
610  }
611 
613  template <Automaton A1, Automaton A2, Automaton A3, Automaton... Auts>
614  auto
615  infiltration(const A1& a1, const A2& a2, const A3& a3, const Auts&... as)
616  -> decltype(infiltration(infiltration(a1, a2), a3, as...))
617  {
618  return infiltration(infiltration(a1, a2), a3, as...);
619  }
620 
621  namespace dyn
622  {
623  namespace detail
624  {
626  template <typename Auts, size_t... I>
627  automaton
628  infiltration_(const std::vector<automaton>& as,
630  {
631  auto res
632  = vcsn::infiltration(as[I]->as<tuple_element_t<I, Auts>>()...);
633  return make_automaton(res);
634  }
635 
637  template <typename Auts>
638  automaton
639  infiltration(const std::vector<automaton>& as)
640  {
641  auto indices
643  return infiltration_<Auts>(as, indices);
644  }
645  }
646  }
647 
648  /*----------------------------------------.
649  | infiltration(expression, expression). |
650  `----------------------------------------*/
651 
653  template <typename ValueSet>
654  typename ValueSet::value_t
655  infiltration(const ValueSet& vs,
656  const typename ValueSet::value_t& lhs,
657  const typename ValueSet::value_t& rhs)
658  {
659  return vs.infiltration(lhs, rhs);
660  }
661 
662  namespace dyn
663  {
664  namespace detail
665  {
667  template <typename ExpSetLhs, typename ExpSetRhs>
668  expression
670  {
671  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
672  return make_expression(std::get<0>(join_elts),
673  ::vcsn::infiltration(std::get<0>(join_elts),
674  std::get<1>(join_elts),
675  std::get<2>(join_elts)));
676  }
677  }
678  }
679 
680 
681  /*-----------------------------.
682  | conjunction(automaton, n). |
683  `-----------------------------*/
684 
685  template <Automaton Aut>
686  auto
687  conjunction(const Aut& aut, unsigned n)
689  {
690  auto res = make_fresh_automaton(aut);
691  {
692  // automatonset::one().
693  auto s = res->new_state();
694  res->set_initial(s);
695  res->set_final(s);
696  for (auto l: res->context().labelset()->generators())
697  res->new_transition(s, s, l);
698  }
699 
700  if (n)
701  {
702  // FIXME: for 1, we should return the accessible part only.
703  static bool iterative = getenv("VCSN_ITERATIVE");
704  if (iterative)
705  for (size_t i = 0; i < n; ++i)
706  res = strip(conjunction(res, aut));
707  else
708  {
709  auto power = strip(aut);
710  while (true)
711  {
712  if (n % 2)
713  res = strip(conjunction(res, power));
714  n /= 2;
715  if (!n)
716  break;
717  power = strip(conjunction(power, power));
718  }
719  }
720  }
721 
722  return res;
723  }
724 
725 
726  namespace dyn
727  {
728  namespace detail
729  {
731  template <Automaton Aut, typename Unsigned>
732  automaton
733  conjunction_repeated(const automaton& aut, unsigned n)
734  {
735  const auto& a = aut->as<Aut>();
736  return make_automaton(::vcsn::conjunction(a, n));
737  }
738  }
739  }
740 
741  /*-----------------------------.
742  | conjunction(value, value). |
743  `-----------------------------*/
744 
746  template <typename ValueSet>
747  typename ValueSet::value_t
748  conjunction(const ValueSet& rs,
749  const typename ValueSet::value_t& lhs,
750  const typename ValueSet::value_t& rhs)
751  {
752  return rs.conjunction(lhs, rhs);
753  }
754 
755  /*---------------------------------------.
756  | conjunction(expression, expression). |
757  `---------------------------------------*/
758 
759  namespace dyn
760  {
761  namespace detail
762  {
764  template <typename ExpSetLhs, typename ExpSetRhs>
765  expression
767  {
768  auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
769  return make_expression(std::get<0>(join_elts),
770  ::vcsn::conjunction(std::get<0>(join_elts),
771  std::get<1>(join_elts),
772  std::get<2>(join_elts)));
773  }
774  }
775  }
776 
777  /*---------------------------------------.
778  | conjunction(polynomial, polynomial). |
779  `---------------------------------------*/
780 
781  namespace dyn
782  {
783  namespace detail
784  {
786  template <typename PolynomialSetLhs, typename PolynomialSetRhs>
787  polynomial
789  {
790  auto join_elts = join<PolynomialSetLhs, PolynomialSetRhs>(lhs, rhs);
791  return make_polynomial(std::get<0>(join_elts),
792  ::vcsn::conjunction(std::get<0>(join_elts),
793  std::get<1>(join_elts),
794  std::get<2>(join_elts)));
795  }
796  }
797  }
798 }
void shuffle()
Compute the (accessible part of the) shuffle product.
Definition: conjunction.hh:109
ValueSet::value_t tuple(const ValueSet &vs, const typename ValueSets::value_t &...v)
Definition: tuple.hh:43
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:195
typename super_t::state_name_t state_name_t
Definition: conjunction.hh:44
constexpr std::enable_if_t<!labelset_t_of< Aut_ >::has_one(), bool > is_spontaneous_in(const Aut_ &, state_t_of< Aut_ >) const
Check if the state has only incoming spontaneous transitions.
Definition: conjunction.hh:309
std::shared_ptr< const detail::polynomial_base > polynomial
Definition: fwd.hh:70
labelset_t_of< context_t > labelset_t
Definition: conjunction.hh:72
Decorator implementing the laziness for an algorithm.
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
void initialize_conjunction()
Fill the worklist with the initial source-state pairs, as needed for the conjunction algorithm...
Definition: conjunction.hh:174
auto make_product_automaton(Aut aut, const Auts &...auts) -> product_automaton< Lazy, Aut, Auts... >
Definition: conjunction.hh:433
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
auto conjunction(const Auts &...as) -> tuple_automaton< decltype(meet_automata(as...)), Auts... >
Build the (accessible part of the) conjunction.
Definition: conjunction.hh:448
auto all_in(Args &&...args) const -> decltype(aut_-> all_in(std::forward< Args >(args)...))
expression infiltration_expression(const expression &lhs, const expression &rhs)
Bridge (infiltration).
Definition: conjunction.hh:669
auto conjunction_lazy(const Auts &...as) -> product_automaton< true, decltype(meet_automata(as...)), Auts... >
Build the (accessible part of the) conjunction, on-the-fly.
Definition: conjunction.hh:461
polynomial make_polynomial(const PolynomialSet &ps, const typename PolynomialSet::value_t &p)
Definition: polynomial.hh:103
auto infiltration(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:603
Definition: a-star.hh:8
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
polynomial conjunction_polynomial(const polynomial &lhs, const polynomial &rhs)
Bridge (conjunction).
Definition: conjunction.hh:788
state_t state(Args &&...args)
Conversion from state name to state number.
context_t_of< Aut > context_t
The context of the result.
Definition: conjunction.hh:71
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: conjunction.hh:64
std::enable_if_t<!L::has_one(), void > maybe_add_one_transitions_(const L &, const state_t, const state_name_t &)
In the case where the labelset doesn't have one, do nothing.
Definition: conjunction.hh:234
std::enable_if_t< labelset_t_of< Aut_ >::has_one(), bool > is_spontaneous_in(const Aut_ &rhs, state_t_of< Aut_ > rst) const
Whether the state has only incoming spontaneous transitions.
Definition: conjunction.hh:321
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:349
std::remove_cv_t< std::remove_reference_t< T >> base_t
T without reference or const/volatile qualifiers.
Definition: traits.hh:12
automaton infiltration_(const std::vector< automaton > &as, vcsn::detail::index_sequence< I... >)
Variadic bridge helper.
Definition: conjunction.hh:628
typename labelset_t::value_t label_t
Definition: conjunction.hh:75
std::tuple< typename transition_map_t< Auts >::map_t &... > out_(const state_name_t &ss)
The outgoing tuple of transitions from state tuple ss.
Aut automaton_t
The type of the resulting automaton.
Definition: conjunction.hh:38
void infiltration()
Compute the (accessible part of the) infiltration product.
Definition: conjunction.hh:122
automaton_t aut_
The wrapped automaton, possibly const.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
auto insplit(Aut &aut) -> std::enable_if_t< labelset_t_of< Aut >::has_one(), decltype(make_insplit_automaton(aut))>
Definition: insplit.hh:291
An input/output format for valuesets.
Definition: format.hh:11
tuple_automaton< automaton_t, Auts... > tuple_automaton_t
Definition: conjunction.hh:39
typename tuple_automaton_t::element_type::template seq< I... > seq
Definition: conjunction.hh:52
bool has_only_one_out(const state_name_t &psrc, std::size_t i, seq< I... >)
Check if all the tapes before the Ith have only outgoing spontaneous transitions. ...
Definition: conjunction.hh:276
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:362
std::enable_if_t< L, void > complete_(state_t s) const
Complete a state: find its outgoing transitions.
product_automaton_impl(Aut aut, const Auts &...auts)
Build a product automaton.
Definition: conjunction.hh:90
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
std::shared_ptr< detail::tuple_automaton_impl< Auts... >> tuple_automaton
A tuple automaton as a shared pointer.
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:165
void cross_tuple(Fun f, const std::tuple< Ts... > &ts)
Definition: tuple.hh:235
typename std::tuple_element< I, T >::type tuple_element_t
C++14.
Definition: tuple.hh:14
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
automaton conjunction_repeated(const automaton &aut, unsigned n)
Bridge (conjunction).
Definition: conjunction.hh:733
Build the (accessible part of the) product.
Definition: conjunction.hh:31
std::tuple< transition_map_t< Auts >... > transition_maps_
Transition caches.
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:220
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:74
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
auto rs
Definition: lift.hh:151
bool has_one_in(const state_name_t &psrc, std::size_t i, seq< I... >) const
Check if all the tapes after the Ith have only incoming spontaneous transitions.
Definition: conjunction.hh:262
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:389
std::enable_if_t< L::has_one(), void > maybe_add_one_transitions_(const L &ls, const state_t src, const state_name_t &psrc)
If the labelset has one, add the relevant spontaneous-transitions leaving the state.
Definition: conjunction.hh:241
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:57
auto labelset(Args &&...args) const -> decltype(aut_-> labelset(std::forward< Args >(args)...))
static symbol sname_(const T &...t)
auto new_transition(Args &&...args) -> decltype(aut_-> new_transition(std::forward< Args >(args)...))
typename super_t::state_t state_t
Definition: conjunction.hh:45
void conjunction()
Compute the (accessible part of the) conjunction.
Definition: conjunction.hh:95
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:53
typename tuple_automaton_t::element_type::state_t state_t
product_automaton_impl self_t
Definition: conjunction.hh:40
base_t< tuple_element_t< I, automata_t >> input_automaton_t
The type of the Ith input automaton, unqualified.
Definition: conjunction.hh:83
typename tuple_automaton_t::element_type::state_name_t state_name_t
std::shared_ptr< const node< Context >> expression
Definition: fwd.hh:182
automaton conjunction_(const std::vector< automaton > &as, bool lazy, vcsn::detail::index_sequence< I... >)
Bridge helper.
Definition: conjunction.hh:494
auto add_transition(Args &&...args) -> decltype(aut_-> add_transition(std::forward< Args >(args)...))
auto join_automata(Auts &&...auts) -> decltype(make_mutable_automaton(join(auts->context()...)))
An automaton whose type is the join between those of auts.
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:90
automaton shuffle_(const std::vector< automaton > &as, vcsn::detail::index_sequence< I... >)
Variadic bridge helper.
Definition: conjunction.hh:543
typename super_t::template transition_map_t< A > transition_map_t
Definition: conjunction.hh:48
constexpr bool all_()
Definition: tuple.hh:404
std::shared_ptr< detail::expression_base > expression
Definition: expression.hh:92
expression shuffle_expression(const expression &lhs, const expression &rhs)
Bridge (shuffle).
Definition: conjunction.hh:584
zipped_maps< Dereference, Maps... > zip_map_tuple(const std::tuple< Maps... > &maps)
Definition: zip-maps.hh:257
weightset_t_of< context_t > weightset_t
Definition: conjunction.hh:73
#define Automaton
Definition: automaton.hh:24
std::tuple< Auts... > automata_t
The type of input automata.
Definition: conjunction.hh:79
auto meet_automata(Auts &&...auts) -> decltype(make_mutable_automaton(meet(auts->context()...)))
An automaton whose type is the meet between those of auts.
const weightset_t & ws_
The resulting weightset.
autodecltype(insplit(aut)) std::enable_if_t<!labelset_t_of< Aut >::has_one()||I==0, Aut & > do_insplit(Aut &aut)
Definition: conjunction.hh:486
auto shuffle(const Auts &...as) -> tuple_automaton< decltype(join_automata(as...)), Auts... >
The (accessible part of the) shuffle product.
Definition: conjunction.hh:527
bool has_only_ones_out(const state_name_t &psrc)
Whether the Ith state of psrc in the Ith input automaton has no non-spontaneous outgoing transitions...
Definition: conjunction.hh:332
expression make_expression(const ExpSet &rs, const typename ExpSet::value_t &r)
Definition: expression.hh:97
expression conjunction_expression(const expression &lhs, const expression &rhs)
Bridge (conjunction).
Definition: conjunction.hh:766
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:299
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:290
std::shared_ptr< detail::product_automaton_impl< Lazy, Aut, Auts... >> product_automaton
A product automaton as a shared pointer.
Definition: conjunction.hh:428
void initialize_shuffle()
Fill the worklist with the initial source-state pairs, as needed for the shuffle algorithm.
Definition: conjunction.hh:181
typename weightset_t::value_t weight_t
Definition: conjunction.hh:76