Vcsn  2.4
Be Rational
universal.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vcsn/algos/copy.hh> // make_fresh_automaton
6 #include <vcsn/weightset/fwd.hh> // b
7 
8 namespace vcsn
9 {
10  namespace detail
11  {
13  template <Automaton Aut>
15  {
16  public:
17  static_assert(labelset_t_of<Aut>::is_free(),
18  "universal: requires free labelset");
19  static_assert(std::is_same<weightset_t_of<Aut>, b>::value,
20  "universal: requires Boolean weights");
21 
22  using automaton_t = Aut;
24  using state_set_t = std::set<state_t>;
25  using pstate_t = std::set<state_set_t>;
26  using map_t = std::map<state_t, state_set_t>;
27 
29  automaton_t operator()(const Aut& automaton)
30  {
31  if (!is_deterministic(automaton))
32  return work_(determinize(automaton)->strip());
33  else if (!is_complete(automaton))
34  return work_(complete(automaton));
35  else
36  return work_(automaton);
37  }
38 
39  private:
44  {
45  // The initial state of automaton.
46  state_t i = aut->dst_of(initial_transitions(aut).front());
47 
48  // compute the co-determinized of the minimal automaton
49  // and retrieve the origin of each state.
50  map_t origin = [&aut]
51  {
52  const auto transposed = transpose(aut);
53  auto codet = determinize(transposed);
54  auto res = map_t{};
55  for (const auto& p: codet->origins())
56  if (p.first != codet->pre()
57  && p.first != codet->post())
58  {
59  auto from = std::set<state_t>{};
60  for (auto sw: p.second)
61  from.emplace(label_of(sw));
62  res.emplace(p.first, std::move(from));
63  }
64  return res;
65  }();
66 
67  // the 'origin' is a map from co_det's state_t to
68  // minimal's state_set_t.
69  // let 'transp_states' be the image of 'origin'.
70  pstate_t transp_states = image(origin);
71 
72  // the universal automaton's state set is its intersection closure.
73  pstate_t univers_states = intersection_closure(transp_states);
74 
75  // The universal automaton.
77 
78  // The final states of aut.
79  auto automaton_finals = std::set<state_t>{};
80  for (auto t: final_transitions(aut))
81  automaton_finals.insert(aut->src_of(t));
82 
83  // we have to save the state set associated to each automaton.
84  map_t subset_label;
85 
86  // X = univers_states \ {}.
87  for (const auto s: univers_states)
88  if (!s.empty())
89  {
90  state_t new_s = res->new_state();
91  subset_label[new_s] = s;
92  // J = { X | i in X }
93  if (has(s, i))
94  res->set_initial(new_s);
95  // U = { X | X \subset T }
96  if (subset(s, automaton_finals))
97  res->set_final(new_s);
98  }
99 
100  // Finally, the transition set.
101  for (const auto x: res->states())
102  for (const auto y: res->states())
103  for (const auto a: *res->labelset())
104  {
105  bool cont = false;
106  state_set_t delta_ret;
107  for (auto s: subset_label[x])
108  {
109  bool empty = true;
110  for (auto t: out(aut, s, a))
111  {
112  empty = false;
113  delta_ret.insert(aut->dst_of(t));
114  }
115  if (empty)
116  {
117  cont = true;
118  break;
119  }
120  }
121  // case 1: \exists p \in X, p.a = {}
122  if (cont)
123  continue;
124  // case 2: X.a \subset Y?
125  if (subset(delta_ret, subset_label[y]))
126  res->new_transition(x, y, a);
127  }
128  return res;
129  }
130  };
131  }
132 
133  template <Automaton Aut>
134  Aut
135  universal(const Aut& a)
136  {
138  return universal(a);
139  }
140 
141  namespace dyn
142  {
143  namespace detail
144  {
146  template <Automaton Aut>
147  automaton
148  universal(const automaton& aut)
149  {
150  const auto& a = aut->as<Aut>();
152  }
153  }
154  }
155 }
Functor for universal.
Definition: universal.hh:14
Container::value_type front(const Container &container)
The first member of this Container.
Definition: algorithm.hh:68
Aut universal(const Aut &a)
Definition: universal.hh:135
return res
Definition: multiply.hh:398
std::set< std::set< T, Compare, Alloc > > intersection_closure(std::set< std::set< T, Compare, Alloc >> pset)
The set of all the intersections of the sets in pset.
Definition: set.hxx:17
bool is_deterministic(const Aut &aut, state_t_of< Aut > s)
Whether state s is deterministic in aut.
auto determinize(const Aut &a, Tag={}, bool_constant< Lazy >={})
Definition: determinize.hh:247
automaton universal(const automaton &aut)
Bridge.
Definition: universal.hh:148
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:177
auto strip(const Aut &aut, int) -> decltype(aut->strip())
Definition: strip.hh:15
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:166
bool is_complete(const Aut &aut)
Whether aut is complete.
Definition: is-complete.hh:14
Definition: a-star.hh:8
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
auto complete(const Aut &aut) -> decltype(::vcsn::copy(aut))
A complete copy of aut.
Definition: complete.hh:65
std::set< state_set_t > pstate_t
Definition: universal.hh:25
std::set< typename std::map< Key, Value, Comp, Alloc >::mapped_type > image(const std::map< Key, Value, Comp, Alloc > &m)
The set of values of a map.
Definition: map.hh:46
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:91
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
automaton_t operator()(const Aut &automaton)
The universal automaton of automaton.
Definition: universal.hh:29
bool subset(const Container &set1, const Container &set2) ATTRIBUTE_PURE
Whether set1 ⊆ set2.
Definition: set.hxx:48
state_t_of< automaton_t > state_t
Definition: universal.hh:23
automaton_t work_(const automaton_t &aut)
Work on aut, which is complete and deterministic.
Definition: universal.hh:43
std::map< state_t, state_set_t > map_t
Definition: universal.hh:26
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
std::set< state_t > state_set_t
Definition: universal.hh:24
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
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253