Vaucanson  1.4.1
eps_removal.hxx
1 // eps_removal.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2004, 2005, 2006, 2008, 2010, 2011 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 #ifndef VCSN_ALGORITHMS_EPS_REMOVAL_HXX
18 # define VCSN_ALGORITHMS_EPS_REMOVAL_HXX
19 
20 # include <vaucanson/algorithms/eps_removal.hh>
21 
22 # include <vaucanson/automata/concept/automata_base.hh>
23 # include <vaucanson/algebra/concept/freemonoid_product.hh>
24 # include <vaucanson/misc/usual_macros.hh>
25 
26 # include <list>
27 # include <map>
28 # include <utility>
29 
30 namespace vcsn {
31 
32  // For automata.
33  template <class A, typename M, typename AI>
34  bool
35  do_is_proper(const AutomataBase<A>&, const M&, const Element<A, AI>& a)
36  {
37  BENCH_TASK_SCOPED("is_proper (automaton)");
38  typedef Element<A, AI> automaton_t;
39  AUTOMATON_TYPES(automaton_t);
40 
41  for_all_const_transitions(e, a)
42  {
43  // A transition labelled by "1+a" is not considered to be
44  // spontaneous by is_spontaneous(), yet it cannot belong to a
45  // proper automaton.
46  series_set_elt_t label = a.series_of(*e);
47  for_all_const_(series_set_elt_t::support_t, it, label.supp())
48  if ((*it).empty())
49  return false;
50  }
51  return true;
52  }
53 
54  // For FMP.
55  template <class A, typename F, typename S, typename AI>
56  bool
57  do_is_proper(const AutomataBase<A>&,
58  const algebra::FreeMonoidProduct<F, S>&,
59  const Element<A, AI>& a)
60  {
61  BENCH_TASK_SCOPED("is_proper (FMP)");
62  typedef Element<A, AI> automaton_t;
63  AUTOMATON_TYPES(automaton_t);
64 
65  for_all_const_transitions(e, a)
66  {
67  series_set_elt_t label = a.series_of(*e);
68  for_all_const_(series_set_elt_t::support_t, it, label.supp())
69  if ((*it).first.empty() && (*it).second.empty())
70  return false;
71  }
72  return true;
73  }
74 
75  template <typename A, typename AI>
76  bool
77  is_proper(const Element<A, AI>& a)
78  {
79  return do_is_proper(a.structure(), a.series().monoid(), a);
80  }
81 
82 
83  // Forward declaration.
84  template <class A_, typename Auto, typename Weight>
85  class EpsilonRemover;
86 
87  template <class A_, typename Auto, typename Weight, int>
88  struct test_for_non_positive_semiring
89  {
90  bool run(const Auto&) const
91  {
92  return true;
93  }
94  };
95 
96  template <class A_, typename Auto, typename Weight>
97  struct test_for_non_positive_semiring<A_, Auto, Weight, 0>
98  {
99  bool run(const Auto& a) const; // See After the EpsilonRemover declaration.
100  };
101 
102  /*--------------------------------------.
103  | EpsilonRemover for weighted automaton |
104  `--------------------------------------*/
105 
106  template <class A_, typename Auto, typename Weight>
107  class EpsilonRemover
108  {
109  AUTOMATON_TYPES(Auto);
110  typedef typename series_set_elt_t::support_t support_t;
111 
112  friend struct test_for_non_positive_semiring
113  <A_, Auto, Weight, semiring_traits<semiring_t,
114  semiring_elt_value_t>::is_positive>;
115 
116 
117  automaton_t& a;
118  // zero and identity of used algebraic structure.
119  series_set_elt_t null_series;
120  semiring_elt_t semiring_elt_zero,
121  semiring_elt_unit;
122  monoid_elt_t monoid_identity;
123 
124 
125  public:
126  EpsilonRemover(const AutomataBase<A_>&,
127  Auto& aut)
128  : a(aut),
129  null_series(aut.series().zero_),
130  semiring_elt_zero(aut.series().semiring().wzero_),
131  semiring_elt_unit(aut.series().semiring().wone_),
132  monoid_identity(aut.series().monoid().VCSN_EMPTY_)
133  {}
134 
135  void operator()(misc::direction_type dir)
136  {
137  test_for_non_positive_semiring
138  <A_, Auto, Weight, semiring_traits<semiring_t,
139  semiring_elt_value_t>::is_positive>
140  nps;
141  result_not_computable_if(!nps.run(a));
142  std::list<hstate_t> eps_states;
143  if (dir == misc::backward)
144  this->epsilon_covering(eps_states);
145  else
146  this->epsilon_co_covering(eps_states);
147  result_not_computable_if(!spontaneous_suppression(eps_states));
148  merge_transitions();
149  }
150 
151  private:
152 
153  /* This method computes a covering of the automaton such
154  that, in this covering, there are two kinds of states:
155  -- states whose incoming transitions are not spontaneous;
156  -- non initial states whose incoming transitions are spontaneous.
157  The argument is filled with the states which belong to the second kind.
158  */
159  void epsilon_covering(std::list<hstate_t>& spontaneous_states)
160  {
161  //list of states to split
162  std::list<hstate_t> split_states;
163  for_all_states(s, a)
164  {
165  bool eps_in = false;
166  bool other_in = a.is_initial(*s);
167 
168  // Test whether there are different types of incoming transitions.
169 
170  std::list<htransition_t> transitions;
171  for (rdelta_iterator e(a.value(), *s); ! e.done(); e.next())
172  transitions.push_back(*e);
173  for_all_(std::list<htransition_t>, e, transitions)
174  {
175  series_set_elt_t t = a.series_of(*e);
176  semiring_elt_t eps_weight= t.get(monoid_identity);
177  if (eps_weight == semiring_elt_zero)
178  other_in = true ;
179  else
180  {
181  eps_in=true;
182  if (t.supp().size() > 1)
183  other_in = true;
184  }
185  }
186  if (eps_in)
187  {
188  if (other_in)
189  split_states.push_back(*s);
190  else
191  spontaneous_states.push_back(*s);
192  }
193  }
194  //Split the states which have to
195  for_all_(std::list<hstate_t>, s, split_states)
196  {
197  hstate_t eps_state = a.add_state();
198  spontaneous_states.push_back(eps_state);
199  //incoming transitions (the original state remains initial if it is)
200  std::list<htransition_t> transitions;
201  for (rdelta_iterator e(a.value(), *s); ! e.done(); e.next())
202  transitions.push_back(*e);
203  for_all_(std::list<htransition_t>, e, transitions)
204  {
205  series_set_elt_t t = a.series_of(*e);
206  semiring_elt_t eps_weight= t.get(monoid_identity);
207  if (eps_weight == semiring_elt_zero)
208  continue;
209  series_set_elt_t eps_label(a.structure().series());
210  eps_label.assoc(monoid_identity.value(), eps_weight.value());
211  //which remains on the transition without epsilon:
212  t.assoc(monoid_identity.value(), semiring_elt_zero.value());
213  hstate_t source=a.src_of(*e);
214  a.add_series_transition(source, eps_state, eps_label);
215  if (t != null_series)
216  a.add_series_transition(source, *s, t);
217  a.del_transition(*e);
218  }
219  //outgoing transitions and final states
220  if (a.is_final(*s))
221  a.set_final(eps_state,a.get_final(*s));
222  for (delta_iterator e(a.value(), *s); ! e.done(); e.next())
223  a.add_series_transition(eps_state, a.dst_of(*e), a.series_of(*e));
224  /* Notice that if there is a loop on *s, with label a+1, the
225  step "incoming transitions" turns it into a loop with
226  label 'a' and a transition from *s to eps_state with
227  label 1, and the step "outgoing transitions" build a
228  transition from eps_state to *s with label '1' and a loop
229  on eps_state with label 1, which is what it is
230  expected */
231  }
232  }
233 
234  /* Initial and final cleaner. This method adds if necessary an
235  initial and/or a final state such that series labelling initial
236  and final arrows are constant. This method is presently unused.
237  */
238  void initial_final_cleaner()
239  {
240  {
241  //Initial
242  std::list<hstate_t> initial_states;
243  for_all_initial_states(s, a)
244  initial_states.push_back(*s);
245  hstate_t new_initial=a.add_state();
246  for_all_(std::list<hstate_t>, s, initial_states)
247  {
248  series_set_elt_t t = a.get_initial(*s);
249  semiring_elt_t eps_weight= t.get(monoid_identity);
250  t.assoc(monoid_identity, semiring_elt_zero.value());
251  if (t != null_series)
252  {
253  a.unset_initial(*s);
254  a.add_series_transition(new_initial, *s, t);
255  if (eps_weight != semiring_elt_zero)
256  {
257  series_set_elt_t cst(a.structure().series());
258  cst.assoc(monoid_identity, eps_weight.value());
259  a.set_initial(*s, cst);
260  }
261  }
262  }
263  delta_iterator test(a.value(), new_initial);
264  if (test.done())
265  a.del_state(new_initial);
266  else
267  a.set_initial(new_initial);
268  }
269  {
270  //Final
271  std::list<hstate_t> final_states;
272  for_all_final_states(s, a)
273  final_states.push_back(*s);
274  hstate_t new_final=a.add_state();
275  for_all_(std::list<hstate_t>, s, final_states)
276  {
277  series_set_elt_t t = a.get_final(*s);
278  semiring_elt_t eps_weight= t.get(monoid_identity);
279  t.assoc(monoid_identity, semiring_elt_zero.value());
280  if (t != null_series)
281  {
282  a.unset_final(*s);
283  a.add_series_transition(*s, new_final, t);
284  if(eps_weight != semiring_elt_zero)
285  {
286  series_set_elt_t cst(a.structure().series());
287  cst.assoc(monoid_identity, eps_weight.value());
288  a.set_final(*s, cst);
289  }
290  }
291  }
292  rdelta_iterator test(a.value(), new_final);
293  if (test.done())
294  a.del_state(new_final);
295  else
296  a.set_final(new_final);
297  }
298  }
299 
300  /* This method computes a co-covering of the automaton such
301  that, in this co-covering, there are two kinds of states:
302  -- states whose outgoing transitions are not spontaneous;
303  -- non final states whose outgoing transitions are spontaneous.
304  The argument is filled with the states which belong to the second kind.
305  */
306  void epsilon_co_covering(std::list<hstate_t>& spontaneous_states)
307  {
308  //list of states to split
309  std::list<hstate_t> split_states;
310  for_all_states(s, a)
311  {
312  bool eps_out = false;
313  bool other_out = a.is_final(*s);
314 
315  // Test whether there are different types of outgoing transitions.
316 
317  std::list<htransition_t> transitions;
318  for (delta_iterator e(a.value(), *s); !e.done(); e.next())
319  transitions.push_back(*e);
320  for_all_(std::list<htransition_t>, e, transitions)
321  {
322  series_set_elt_t t = a.series_of(*e);
323  semiring_elt_t eps_weight= t.get(monoid_identity);
324  if(eps_weight == semiring_elt_zero)
325  other_out=true ;
326  else
327  {
328  eps_out=true;
329  if (t.supp().size() > 1)
330  other_out=true;
331  }
332  }
333  if (eps_out)
334  {
335  if (other_out)
336  split_states.push_back(*s);
337  else
338  spontaneous_states.push_back(*s);
339  }
340  }
341  //Split the states which have to
342  for_all_(std::list<hstate_t>, s, split_states)
343  {
344  hstate_t eps_state = a.add_state();
345  spontaneous_states.push_back(eps_state);
346  //outgoing transitions (the original state remains final if it is)
347  std::list<htransition_t> transitions;
348  for (delta_iterator e(a.value(), *s); !e.done(); e.next())
349  transitions.push_back(*e);
350  for_all_(std::list<htransition_t>, e, transitions)
351  {
352  series_set_elt_t t = a.series_of(*e);
353  semiring_elt_t eps_weight= t.get(monoid_identity);
354  if (eps_weight == semiring_elt_zero)
355  continue;
356  series_set_elt_t eps_label(a.structure().series());
357  eps_label.assoc(monoid_identity.value(), eps_weight.value());
358  //which remains on the transition without epsilon:
359  t.assoc(monoid_identity.value(), semiring_elt_zero.value());
360  hstate_t target=a.dst_of(*e);
361  a.add_series_transition(eps_state, target, eps_label);
362  if (t != null_series)
363  a.add_series_transition(*s, target, t);
364  a.del_transition(*e);
365  }
366  //incoming transitions and initial states
367  if (a.is_initial(*s))
368  a.set_initial(eps_state,a.get_initial(*s));
369  for (rdelta_iterator e(a.value(), *s); ! e.done(); e.next())
370  a.add_series_transition(a.src_of(*e), eps_state, a.series_of(*e));
371  /* Notice that if there is a loop on *s, with label a+1, the
372  step "outgoing transitions" turns it into a loop with
373  label 'a' and a transition from eps_state to *s with
374  label 1, and the step "incoming transitions" build a
375  transition from *s to eps_state with label '1' and a loop
376  on eps_state with label 1, which is what it is
377  expected */
378  }
379  }
380 
381  /* This method computes an equivalent K-automaton with only
382  positive transitions (excepted final arrows). A second copy of
383  the automaton is built, a negative weight makes switch from a
384  copy to another. Two final states are added, one where
385  positive paths end, the other one where negative paths end. In
386  the result, all the edges have positive weight; the two final
387  states have resp. weights equal to 1 and -1.
388  */
389  void positive_path_covering()
390  {
391  std::map<hstate_t,hstate_t> clones;
392  std::list<hstate_t> states;
393  for_all_states(s, a)
394  states.push_back(*s);
395  for_all_(std::list<hstate_t>, s, states)
396  clones[*s]=a.add_state();
397  hstate_t pos_final_state=a.add_state();
398  hstate_t neg_final_state=a.add_state();
399  std::list<htransition_t> transitions;
400  for_all_transitions(e, a)
401  transitions.push_back(*e);
402  for_all_(std::list<htransition_t>, e, transitions)
403  {
404  series_set_elt_t posit = a.series_of(*e);
405  series_set_elt_t negat(a.structure().series());
406  support_t su = posit.supp();
407  for_all_(support_t, x, su)
408  {
409  semiring_elt_t weight=posit.get(*x);
410  if (weight < semiring_elt_zero)
411  {
412  negat.assoc(*x,-weight.value());
413  posit.assoc(*x,semiring_elt_zero.value());
414  }
415  }
416  hstate_t src=a.src_of(*e), dst=a.dst_of(*e);
417  if (posit != null_series)
418  a.add_series_transition(clones[src], clones[dst], posit);
419  if (negat != null_series)
420  {
421  a.add_series_transition(src, clones[dst], negat);
422  a.add_series_transition(clones[src], dst, negat);
423  if (posit != null_series)
424  a.add_series_transition(src, dst, posit);
425  a.del_transition(*e);
426  }
427  }
428  states.clear();
429  for_all_initial_states(s, a)
430  states.push_back(*s);
431  for_all_(std::list<hstate_t>, s, states)
432  {
433  series_set_elt_t posit = a.get_initial(*s);
434  series_set_elt_t negat(a.structure().series());
435  support_t su = posit.supp();
436  for_all_(support_t, x, su)
437  {
438  semiring_elt_t weight = posit.get(*x);
439  if (weight < semiring_elt_zero)
440  {
441  negat.assoc(*x,-weight.value());
442  posit.assoc(*x,semiring_elt_zero.value());
443  }
444  }
445  if (negat != null_series)
446  {
447  a.set_initial(clones[*s], negat);
448  a.unset_initial(*s);
449  if (posit != null_series)
450  a.set_initial(*s,posit);
451  }
452  }
453  states.clear();
454  for_all_final_states(s, a)
455  states.push_back(*s);
456  for_all_(std::list<hstate_t>, s, states)
457  {
458  series_set_elt_t posit = a.get_final(*s);
459  series_set_elt_t negat(a.structure().series());
460  support_t su = posit.supp();
461  for_all_(support_t, x, su)
462  {
463  semiring_elt_t weight=posit.get(*x);
464  if (weight < semiring_elt_zero)
465  {
466  negat.assoc(*x,-weight.value());
467  posit.assoc(*x,semiring_elt_zero.value());
468  }
469  }
470  if (negat != null_series)
471  {
472  a.add_series_transition(*s, neg_final_state, negat);
473  a.add_series_transition(clones[*s], pos_final_state, negat);
474  }
475  a.unset_final(*s);
476  if (posit != null_series)
477  {
478  a.add_series_transition(*s, pos_final_state, posit);
479  a.add_series_transition(clones[*s], neg_final_state, posit);
480  }
481  }
482  a.set_final(pos_final_state);
483  series_set_elt_t mss = a.get_final(pos_final_state);
484  mss.assoc(monoid_identity,-semiring_elt_unit.value());
485  a.set_final(neg_final_state,mss);
486  accessible_here(a);
487  }
488 
489  /* This method makes every weight in the K-automaton positive
490  */
491  void absolute_weight()
492  {
493  std::list<htransition_t> transitions;
494  for_all_transitions(e, a)
495  transitions.push_back(*e);
496  for_all_(std::list<htransition_t>, e, transitions)
497  {
498  series_set_elt_t label = a.series_of(*e);
499  support_t support = label.supp();
500  for_all_(support_t, x, support)
501  {
502  semiring_elt_t weight=label.get(*x);
503  if (weight < semiring_elt_zero)
504  label.assoc(*x,-weight.value());
505  }
506  hstate_t src=a.src_of(*e), dst=a.dst_of(*e);
507  a.del_transition(*e);
508  a.add_series_transition(src, dst, label);
509  }
510  std::list<hstate_t> states;
511  for_all_initial_states(s, a)
512  states.push_back(*s);
513  for_all_(std::list<hstate_t>, s, states)
514  {
515  series_set_elt_t label = a.get_initial(*s);
516  support_t support = label.supp();
517  for_all_(support_t, x, support)
518  {
519  semiring_elt_t weight = label.get(*x);
520  if (weight < semiring_elt_zero)
521  label.assoc(*x,-weight.value());
522  }
523  a.set_initial(*s,label);
524  }
525  states.clear();
526  for_all_final_states(s, a)
527  states.push_back(*s);
528  for_all_(std::list<hstate_t>, s, states)
529  {
530  series_set_elt_t label = a.get_final(*s);
531  support_t support = label.supp();
532  for_all_(support_t, x, support)
533  {
534  semiring_elt_t weight = label.get(*x);
535  if (weight < semiring_elt_zero)
536  label.assoc(*x,-weight.value());
537  }
538  a.set_final(*s,label);
539  }
540  }
541 
542  /*supression of "epsilon-states"
543  epsilon_covering should have been called before
544  This part of the algorithm is symmetrical and is exactly
545  the "elimination state method" applicated to a list of states.
546  We consider the case where the state is initial or final, even if
547  in the backward case the 'epsilon state' cannot be initial for instance
548  */
549  bool spontaneous_suppression(std::list<hstate_t>& sp_states)
550  {
551  for_all_(std::list<hstate_t>, s, sp_states)
552  {
553  std::list<htransition_t> incoming_transitions;
554  //list of incoming transitions, beginning with loops
555  for (rdelta_iterator e(a.value(), *s); ! e.done(); e.next())
556  {
557  if (a.src_of(*e) == a.dst_of(*e))
558  incoming_transitions.push_front(*e);
559  else
560  incoming_transitions.push_back(*e);
561  }
562  bool hasloop=false;
563  series_set_elt_t loop_series(a.structure().series());
564  //loops are removed from incoming transitions;
565  while (!incoming_transitions.empty())
566  {
567  htransition_t& loop=incoming_transitions.front();
568  if(a.src_of(loop)==a.dst_of(loop))
569  {
570  hasloop=true;
571  loop_series += a.series_of(loop);
572  incoming_transitions.pop_front();
573  }
574  else
575  break;
576  }
577  if (hasloop)
578  {
579  if (!loop_series.get(monoid_identity).starable())
580  return false;
581  loop_series = loop_series.star();
582  }
583  std::list<htransition_t> outgoing_transitions;
584  for (delta_iterator e(a.value(), *s); ! e.done(); e.next())
585  if (a.src_of(*e)!=a.dst_of(*e))
586  outgoing_transitions.push_back(*e);
587  for_all_(std::list<htransition_t>, e, incoming_transitions)
588  for_all_(std::list<htransition_t>, f, outgoing_transitions)
589  if (hasloop)
590  a.add_series_transition(a.src_of(*e), a.dst_of(*f),
591  a.series_of(*e)*loop_series*a.series_of(*f));
592  else
593  a.add_series_transition(a.src_of(*e), a.dst_of(*f),
594  a.series_of(*e)*a.series_of(*f));
595  if (a.is_final(*s))
596  {
597  series_set_elt_t final_s = a.get_final(*s);
598  for_all_(std::list<htransition_t>, e, incoming_transitions)
599  {
600  hstate_t p = a.src_of(*e);
601  series_set_elt_t t = a.get_final(p);
602  if (hasloop)
603  t += a.series_of(*e)*loop_series*final_s;
604  else
605  t += a.series_of(*e)*final_s;
606  a.unset_final(p);
607  if (t != null_series)
608  a.set_final(p,t);
609  }
610  }
611  if (a.is_initial(*s))
612  {
613  series_set_elt_t initial_s=a.get_initial(*s);
614  for_all_(std::list<htransition_t>, f, outgoing_transitions)
615  {
616  hstate_t p = a.dst_of(*f);
617  series_set_elt_t t = a.get_initial(p);
618  if (hasloop)
619  t += initial_s*loop_series*a.series_of(*f);
620  else
621  t += initial_s*a.series_of(*f);
622  a.unset_initial(p);
623  if (t != null_series)
624  a.set_initial(p,t);
625  }
626  }
627  a.del_state(*s);
628  }
629  return true;
630  }
631 
632  //merge transitions with the same ends
633  void merge_transitions()
634  {
635  typedef std::map<hstate_t, series_set_elt_t> map_t;
636  for_all_states(s, a)
637  {
638  map_t map;
639  std::list<htransition_t> transitions;
640  for (delta_iterator e(a.value(), *s); ! e.done(); e.next())
641  {
642  hstate_t target = a.dst_of(*e);
643  transitions.push_back(*e);
644  typename map_t::iterator it = map.find(target);
645  if (it == map.end())
646  map.insert(std::pair<hstate_t, series_set_elt_t>(target,
647  a.series_of(*e)));
648  else
649  it->second += a.series_of(*e);
650  }
651  for_all_(std::list<htransition_t>, e, transitions)
652  a.del_transition(*e);
653  for_all_(map_t, it, map)
654  if(it->second != null_series)
655  a.add_series_transition(*s, it->first, it->second);
656  }
657  }
658 
659  };
660 
661 
662  template <class A_, typename Auto, typename Weight>
663  bool test_for_non_positive_semiring<A_, Auto, Weight, 0>::run(const Auto& a) const
664  {
665  AUTOMATON_TYPES(Auto);
666 
667  std::list<hstate_t> eps_states;
668  automaton_t test(a);
669  EpsilonRemover<A_, Auto, Weight> epsTest(test.structure(), test);
670  epsTest.absolute_weight();
671  epsTest.epsilon_covering(eps_states);
672  return epsTest.spontaneous_suppression(eps_states);
673  }
674 
675 
676 
677 
678  /*--------------.
679  | eps_removal. |
680  `--------------*/
681 
682  template<class A_, typename Auto, typename Weight>
683  void
684  do_eps_removal_here(const AutomataBase<A_>& a_set,
685  const Weight&,
686  Auto& a,
687  misc::direction_type dir)
688  {
689  BENCH_TASK_SCOPED("eps_removal");
690  AUTOMATON_TYPES(Auto);
691  EpsilonRemover<A_, Auto, Weight> algo(a_set, a);
692  algo(dir);
693  }
694 
695  template<typename A, typename AI>
696  void
697  eps_removal_here(Element<A, AI>& a, misc::direction_type dir)
698  {
699  typedef Element<A, AI> automaton_t;
700  AUTOMATON_TYPES(automaton_t);
701 
702  do_eps_removal_here(a.structure(),
703  SELECT(semiring_elt_value_t),
704  a, dir);
705  }
706 
707  template<typename A, typename AI>
708  Element<A, AI>
709  eps_removal(const Element<A, AI>& a, misc::direction_type dir)
710  {
711  typedef Element<A, AI> automaton_t;
712  AUTOMATON_TYPES(automaton_t);
713 
714  automaton_t ret(a);
715  do_eps_removal_here(ret.structure(),
716  SELECT(semiring_elt_value_t),
717  ret, dir);
718  return ret;
719  }
720 
721  template<typename A, typename AI>
722  void
723  backward_eps_removal_here(Element<A, AI>& a)
724  {
725  typedef Element<A, AI> automaton_t;
726  AUTOMATON_TYPES(automaton_t);
727 
728  do_eps_removal_here(a.structure(),
729  SELECT(semiring_elt_value_t),
730  a, misc::backward);
731  }
732 
733  template<typename A, typename AI>
734  Element<A, AI>
735  backward_eps_removal(const Element<A, AI>& a)
736  {
737  typedef Element<A, AI> automaton_t;
738  AUTOMATON_TYPES(automaton_t);
739 
740  automaton_t ret(a);
741  do_eps_removal_here(ret.structure(),
742  SELECT(semiring_elt_value_t),
743  ret, misc::backward);
744  return ret;
745  }
746 
747  template<typename A, typename AI>
748  void
749  forward_eps_removal_here(Element<A, AI>& a)
750  {
751  typedef Element<A, AI> automaton_t;
752  AUTOMATON_TYPES(automaton_t);
753 
754  do_eps_removal_here(a.structure(),
755  SELECT(semiring_elt_value_t),
756  a, misc::forward);
757  }
758 
759  template<typename A, typename AI>
760  Element<A, AI>
761  forward_eps_removal(const Element<A, AI>& a)
762  {
763  typedef Element<A, AI> automaton_t;
764  AUTOMATON_TYPES(automaton_t);
765 
766  automaton_t ret(a);
767  do_eps_removal_here(ret.structure(),
768  SELECT(semiring_elt_value_t),
769  ret, misc::forward);
770  return ret;
771  }
772 
773 } // vcsn
774 
775 #endif // ! VCSN_ALGORITHMS_EPS_REMOVAL_HXX
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1