Awali
Another Weighted Automata library
aut_to_exp.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_ALGOS_AUT_TO_EXP_HH
18 # define AWALI_ALGOS_AUT_TO_EXP_HH
19 
20 #include <awali/sttc/algos/copy.hh>
21 #include <awali/sttc/algos/lift.hh>
25 
26 namespace awali { namespace sttc {
27 
28 
29  /*----------------.
30  | state_chooser. |
31  `----------------*/
32 
34  template <typename Aut,
35  typename Lifted = internal::lifted_automaton_t<Aut>>
37  std::function<state_t(const Lifted&)>;
38 
39 
40  /*--------------------------.
41  | Naive heuristics degree. |
42  `--------------------------*/
43 
44  template <typename Aut>
45  state_t
46  next_heuristic(const Aut& a)
47  {
48  state_t best = 0;
49  bool best_has_loop = false;
50  size_t best_degree = std::numeric_limits<size_t>::max();
51  for (auto s: a->states())
52  {
53  size_t out = 0;
54  // Since we are in LAO, there can be at most one such loop.
55  bool has_loop = false;
56  // Don't count the loops as out-degree.
57  for (auto t: a->all_out(s))
58  if (a->dst_of(t) != s)
59  ++out;
60  else
61  has_loop = true;
62  size_t in = a->all_in(s).size();
63  size_t degree = in * out;
64  // We prefer to delete a state that has no loop transition.
65  if (degree < best_degree
66  || (degree == best_degree && has_loop < best_has_loop))
67  {
68  best = s;
69  best_degree = degree;
70  best_has_loop = has_loop;
71  }
72  }
73  assert(best);
74  return best;
75  }
76 
77  /*--------------------------.
78  | Choose states in order. |
79  `--------------------------*/
80 
81 /* */
82  template <typename Aut>
83  state_t
84  next_in_order(const Aut& a)
85  {
86  state_t best = 0;
87  for (auto s: a->states())
88  {
89  best = s;
90  }
91  assert(best);
92  return best;
93  }
94 /* */
95 
96  /*------------------.
97  | eliminate_state. |
98  `------------------*/
99 
100  namespace internal
101  {
102  template <typename Aut, typename Kind = typename context_t_of<Aut>::kind_t>
104 
105  template <typename Aut>
107  {
108  static_assert(context_t_of<Aut>::is_lao,
109  "requires labels_are_one");
110 
111  using automaton_t = typename std::remove_cv<Aut>::type;
114  using state_chooser_t = std::function<state_t(const automaton_t&)>;
115 
117  : debug_(0)
118  , aut_(aut)
119  {}
120 
123  {
124  require(aut_->has_state(s), "not a valid state: " + std::to_string(s));
125 
126  // The loop's weight.
127  auto loop = ws_.zero();
128  assert(aut_->outin(s, s).begin()==aut_->outin(s, s).end()
129  || ++(aut_->outin(s, s).begin())==aut_->outin(s, s).end());
130  // There is a single possible loop labeled by \e, but it's
131  // easier and symmetrical with LAR to use a for-loop.
132  for (auto t: to_vector(aut_->outin(s, s)))
133  {
134  loop = ws_.add(loop, aut_->weight_of(t));
135  aut_->del_transition(t);
136  }
137  loop = ws_.star(loop);
138 
139  // Get all the predecessors, and successors, except itself.
140  auto outs = aut_->all_out(s);
141  for (auto in: aut_->all_in(s))
142  for (auto out: outs)
143  aut_->add_transition
144  (aut_->src_of(in), aut_->dst_of(out),
145  aut_->label_of(in),
146  ws_.mul(aut_->weight_of(in), loop, aut_->weight_of(out)));
147  aut_->del_state(s);
148  }
149 
151  void operator()(const state_chooser_t& next_state)
152  {
153  while (aut_->num_states())
154  operator()(next_state(aut_));
155  }
156 
157  private:
159  int debug_;
161  automaton_t& aut_;
163  const weightset_t& ws_ = *aut_->weightset();
164  };
165 
166  template <typename Aut>
168  {
169  static_assert(context_t_of<Aut>::is_lar,
170  "requires labels_are_ratexps");
171  // FIXME: ratexpset<lal_char(a-c)_z>_q for instance cannot work,
172  // because we need to move the q weights inside the
173  // lal_char(a-c)_z ratexps, which obviously not possible. So we
174  // need to require that there is a subtype relationship between
175  // the weightset and the weightset of the ratexp.
176  //
177  // Yet as of 2014-07, there is no means to check that subtype
178  // relationship in Vaucanson.
179 
180  using automaton_t = typename std::remove_cv<Aut>::type;
184  using state_chooser_t = std::function<state_t(const automaton_t&)>;
185 
187  : debug_(0)
188  , aut_(aut)
189  {}
190 
193  {
194  require(aut_->has_state(s), "not a valid state: " + std::to_string(s));
195 
196  // The loops' ratexp.
197  auto loop = rs_.zero();
198  for (auto t: to_vector(aut_->outin(s, s)))
199  {
200  loop = rs_.add(loop,
201  rs_.lmul(aut_->weight_of(t), aut_->label_of(t)));
202  aut_->del_transition(t);
203  }
204  loop = rs_.star(loop);
205 
206  // Get all the predecessors, and successors, except itself.
207  auto outs = aut_->all_out(s);
208  for (auto in: aut_->all_in(s))
209  for (auto out: outs)
210  aut_->add_transition
211  (aut_->src_of(in), aut_->dst_of(out),
212  rs_.mul(rs_.lmul(aut_->weight_of(in), aut_->label_of(in)),
213  loop,
214  rs_.lmul(aut_->weight_of(out), aut_->label_of(out))));
215  aut_->del_state(s);
216  }
217 
219  void operator()(const state_chooser_t& next_state)
220  {
221  while (aut_->num_states())
222  operator()(next_state(aut_));
223  }
224 
225  private:
227  int debug_;
229  automaton_t& aut_;
231  const ratexpset_t& rs_ = *aut_->labelset();
233  const weightset_t& ws_ = *aut_->weightset();
234  };
235  }
236 
237  /*-------------.
238  | aut_to_exp. |
239  `-------------*/
252  template <typename Aut,
253  typename Context = ratexpset_of<context_t_of<Aut>>>
254  typename Context::ratexp_t
255  aut_to_exp(const Aut& a,
256  const state_chooser_t<Aut>& next_state)
257  {
258  // State elimination is performed on the lifted automaton.
259  auto aut = internal::unnormalized_lift(a);
260  internal::state_eliminator<decltype(aut)> eliminate_states(aut);
261  eliminate_states(next_state);
262  return aut->get_initial_weight(aut->post());
263  }
264 
265 
283  template <typename Aut,
284  typename Context = ratexpset_of<context_t_of<Aut>>>
285  typename Context::ratexp_t
286  aut_to_exp(const Aut& a)
287  {
288  state_chooser_t<Aut> next = next_heuristic<internal::lifted_automaton_t<Aut>>;
289  return aut_to_exp(a, next);
290  }
291 
292 
302  template <typename Aut,
303  typename Context = ratexpset_of<context_t_of<Aut>>>
304  typename Context::ratexp_t
305  aut_to_exp_in_order(const Aut& a)
306  {
307  state_chooser_t<Aut> next = next_in_order<internal::lifted_automaton_t<Aut>>;
308  return aut_to_exp(a, next);
309  }
310 
311 
312 }}//end of ns awali::stc
313 
314 #endif // !AWALI_ALGOS_AUT_TO_EXP_HH
internal::lifted_automaton_t< Aut > unnormalized_lift(const Aut &a, bool keep_history=true)
Definition: lift.hh:88
std::vector< typename Cont::value_type > to_vector(const Cont &cont)
Return the content of cont as a vector.
Definition: vector.hh:72
Definition: aut_to_exp.hh:103
std::string to_string(identities i)
Context::ratexp_t aut_to_exp_in_order(const Aut &a)
Basic state elimination algorithm.
Definition: aut_to_exp.hh:305
typename internal::context_t_of_impl< internal::base_t< ValueSet > >::type context_t_of
Helper to retrieve the type of the context of a value set.
Definition: traits.hh:66
typename internal::labelset_t_of_impl< internal::base_t< ValueSet > >::type labelset_t_of
Helper to retrieve the type of the labelset of a value set.
Definition: traits.hh:76
Context::ratexp_t aut_to_exp(const Aut &a, const state_chooser_t< Aut > &next_state)
Generic state elimination algorithm.
Definition: aut_to_exp.hh:255
state_t next_in_order(const Aut &a)
Definition: aut_to_exp.hh:84
std::function< state_t(const Lifted &)> state_chooser_t
A state (inner) from an automaton.
Definition: aut_to_exp.hh:37
state_t next_heuristic(const Aut &a)
Definition: aut_to_exp.hh:46
void require(bool b, Args &&... args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:55
typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type weightset_t_of
Helper to retrieve the type of the weightset of a value set.
Definition: traits.hh:86
ATTRIBUTE_CONST int max(int a, int b)
Definition: arith.hh:54
Main namespace of Awali.
Definition: ato.hh:22
unsigned state_t
Definition: types.hh:21
std::function< state_t(const automaton_t &)> state_chooser_t
State selector type.
Definition: aut_to_exp.hh:114
void operator()(const state_chooser_t &next_state)
Eliminate all the states, in the order specified by next_state.
Definition: aut_to_exp.hh:151
weightset_t_of< automaton_t > weightset_t
Definition: aut_to_exp.hh:112
void operator()(state_t s)
Eliminate state s.
Definition: aut_to_exp.hh:122
typename std::remove_cv< Aut >::type automaton_t
Definition: aut_to_exp.hh:111
state_eliminator(automaton_t &aut)
Definition: aut_to_exp.hh:116
std::function< state_t(const automaton_t &)> state_chooser_t
State selector type.
Definition: aut_to_exp.hh:184
void operator()(const state_chooser_t &next_state)
Eliminate all the states, in the order specified by next_state.
Definition: aut_to_exp.hh:219
labelset_t_of< automaton_t > ratexpset_t
Definition: aut_to_exp.hh:181
state_eliminator(automaton_t &aut)
Definition: aut_to_exp.hh:186
void operator()(state_t s)
Eliminate state s.
Definition: aut_to_exp.hh:192
weightset_t_of< automaton_t > weightset_t
Definition: aut_to_exp.hh:182
typename std::remove_cv< Aut >::type automaton_t
Definition: aut_to_exp.hh:180
marker type for labelsets where labels are one
Definition: kind.hh:80
marker type for labelsets where labels are rational expressions
Definition: kind.hh:82