Vcsn  2.4
Be Rational
reduce.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <map>
4 #include <unordered_map>
5 #include <vector>
6 
7 #include <vcsn/algos/copy.hh>
9 #include <vcsn/core/automaton.hh>
10 #include <vcsn/dyn/automaton.hh>
11 #include <vcsn/weightset/q.hh>
12 #include <vcsn/weightset/r.hh>
13 #include <vcsn/weightset/z.hh>
14 
15 namespace vcsn
16 {
17  namespace detail
18  {
19  /*
20  The core algorithm computes a scaled basis from a list of
21  vectors. There is a permutation on entries in such a way that
22  the first non-zero entry of the i-th vector of the basis has
23  index i. (in the field case, this entry is equal to 1)
24 
25  If v is a new vector, for every vector b_i of the bases:
26 
27  - either v[i] is zero and there is nothing to do
28 
29  - or v[i] is different from 0 in this case, v is modified as v:=
30  v - v[i].b which makes v[i]=0 (in the Z case, b may also be
31  modified) This is performed by the reduce_vector method
32 
33  After the iteration, if v is null, it means that the vector was in the
34  vector space (or the Z-module) generated by the basis.
35  Otherwise, a non zero entry of v is selected (find_pivot),
36  v is normalized (normalization_vector) and the permutation is
37  updated in such a way that the pivot becomes the first non zero
38  entry of v, which is inserted in the basis.
39 
40  Once the basis is stabilized, a bottom-up reduction is applied
41  to the scaled basis in order to make it more "diagonal".
42  Finally, the new automaton is built w.r.t. the computed basis.
43  The construction of the automaton can not be done on-the-fly due
44  to both the Z case where the basis is modified and the bottom-up
45  reduction.
46  */
47 
48 
49  /*
50 
51  The implementation of elementary methods slightly differ
52  w.r.t. the weightset.
53 
54  Generically,
55 
56  find_pivot returns the first non zero entry
57 
58  reduce_vector computes current := current - current[i].b_i
59 
60  normalisation_vector applied a ratio in such a way that
61  the pivot is 1
62 
63  bottom_up_reduction applies, for each vector of the
64  basis, reduce_vector to every preceding vector in the
65  basis.
66 
67 
68  In Q : find_pivot searchs for the entry where
69  |numerator|+|denominator| is minimal
70 
71  In R : find_pivot searchs for the entry x where |x|+1/|x|
72  is minimal
73 
74  In Z : find_pivot searchs for the (non zero) entry x where
75  |x| is minimal
76  reduce_vector both reduce the current and the basis vector
77  (w.r.t. the gcd of current[i] and b_i[i])
78  normalisation_vector does not apply
79  bottom_up_reduction does not apply
80 
81  */
82 
83  template <typename Weightset>
84  struct select
85  {
86  template <typename Reduc, typename Vector>
87  static unsigned
88  find_pivot(Reduc* that, const Vector& v,
89  unsigned begin, unsigned* permutation)
90  {
91  return that->find_pivot(v, begin, permutation);
92  }
93 
94  template <typename Reduc, typename Vector>
95  static void
96  reduce_vector(Reduc* that, Vector& vbasis,
97  Vector& current, unsigned b, unsigned* permutation)
98  {
99  that->reduce_vector(vbasis, current, b, permutation);
100  }
101 
102  template <typename Reduc, typename Vector>
103  static void
104  normalisation_vector(Reduc* that, Vector& v,
105  unsigned pivot, unsigned* permutation)
106  {
107  that->normalisation_vector(v, pivot, permutation);
108  }
109 
110  template <typename Reduc, typename Basis>
111  static void
112  bottom_up_reduction(Reduc* that, Basis& basis, unsigned* permutation)
113  {
114  that->bottom_up_reduction(basis, permutation);
115  }
116 
117  template <typename Reduc, typename Basis, typename Vector>
118  static void
119  vector_in_new_basis(Reduc* that, Basis& basis,
120  Vector& current, Vector& new_vector,
121  unsigned* permutation)
122  {
123  that->vector_in_new_basis(basis, current, new_vector, permutation);
124  }
125  };
126 
127  template <>
128  struct select<q> : select<void>
129  {
130  template <typename Reduc, typename Vector>
131  static unsigned
132  find_pivot(Reduc* that, const Vector& v,
133  unsigned begin, unsigned* permutation)
134  {
135  return that->find_pivot_by_norm(v, begin, permutation);
136  }
137  };
138 
139  template <>
140  struct select<r> : select<void>
141  {
142  template <typename Reduc, typename Vector>
143  static unsigned
144  find_pivot(Reduc* that, const Vector& v,
145  unsigned begin, unsigned* permutation)
146  {
147  return that->find_pivot_by_norm(v, begin, permutation);
148  }
149  };
150 
151  template <>
152  struct select<z> : select<void>
153  {
154  template <typename Reduc, typename Vector>
155  static unsigned
156  find_pivot(Reduc* that, const Vector& v,
157  unsigned begin, unsigned* permutation)
158  {
159  return that->find_pivot_by_norm(v, begin, permutation);
160  }
161 
162  template <typename Reduc, typename Vector>
163  static void
164  reduce_vector(Reduc* that, Vector& vbasis,
165  Vector& current, unsigned b, unsigned* permutation)
166  {
167  that->z_reduce_vector(vbasis, current, b, permutation);
168  }
169 
170  template <typename Reduc, typename Vector>
171  static void normalisation_vector(Reduc*, Vector&, unsigned, unsigned*)
172  {}
173 
174  template <typename Reduc, typename Basis>
175  static void bottom_up_reduction(Reduc*, Basis&, unsigned*)
176  {}
177 
178  template <typename Reduc, typename Basis, typename Vector>
179  static void
180  vector_in_new_basis(Reduc* that, Basis& basis,
181  Vector& current, Vector& new_vector,
182  unsigned* permutation)
183  {
184  that->z_vector_in_new_basis(basis, current, new_vector, permutation);
185  }
186  };
187 
188  template <Automaton Aut>
190  {
191  static_assert(labelset_t_of<Aut>::is_free(),
192  "reduce: requires free labelset");
193 
194  using automaton_t = Aut;
196  using weightset_t = typename context_t::weightset_t;
201  using weight_t = typename context_t::weight_t;
202  using vector_t = std::vector<weight_t>;
203  using matrix_t = std::vector<std::map<std::size_t, weight_t> > ;
204  using matrix_set_t = std::map<label_t, matrix_t>;
205 
206  public:
208  : input_(input)
209  , res_(make_fresh_automaton(input))
210  {}
211 
214  {
215  std::unordered_map<state_t, unsigned> state_to_index;
216  unsigned i = 0;
217  for (auto s: input_->states())
218  state_to_index[s] = i++;
219  dimension = i;
220  if (dimension == 0)
221  return;
222  init.resize(i);
223  final.resize(i);
224  // Computation of the initial vector.
225  for (auto t : initial_transitions(input_))
226  init[state_to_index[input_->dst_of(t)]] = input_->weight_of(t);
227  // Computation of the final vector.
228  for (auto t : final_transitions(input_))
229  final[state_to_index[input_->src_of(t)]] = input_->weight_of(t);
230  // For each letter, we define an adjency matrix.
231  for (auto t : transitions(input_))
232  {
233  auto it = letter_matrix_set.find(input_->label_of(t));
234  if (it == letter_matrix_set.end())
235  it = letter_matrix_set.emplace(input_->label_of(t),
236  matrix_t(dimension)).first;
237  it->second[state_to_index[input_->src_of(t)]]
238  [state_to_index[input_->dst_of(t)]] = input_->weight_of(t);
239  }
240  }
241 
242  //utility methods
243 
246  const matrix_t& m,
247  vector_t& res)
248  {
249  for (unsigned i = 0; i < dimension; i++)
250  for (auto it : m[i])
251  {
252  unsigned j = it.first;
253  res[j] = ws_.add(res[j], ws_.mul(v[i], it.second));
254  }
255  }
256 
259  const vector_t& w)
260  {
261  weight_t res = ws_.zero();
262  for (unsigned i = 0; i < dimension; ++i)
263  res = ws_.add(res, ws_.mul(v[i], w[i]));
264  return res;
265  }
266 
271 
272  /*
273  The pivot is the entry x of the vector such that norm(x) is minimal.
274  This "norm" highly depends on the semiring.
275 
276  For rational numbers, it is the sum of the numerator and the
277  denominator (absolute value)
278 
279  For "real" numbers, it is |x|+|1/x| .
280  */
281 
282  static weight_t norm(const q_weight_t& w)
283  {
284  return w.den+abs(w.num);
285  }
286 
288  static weight_t norm(const r_weight_t& w)
289  {
290  return fabs(w)+fabs(1/w);
291  }
292 
294  static weight_t norm(const z_weight_t& w)
295  {
296  return abs(w);
297  }
298 
299  // Works for both Q and R.
300  unsigned
301  find_pivot_by_norm(const vector_t& v, unsigned begin,
302  unsigned* permutation)
303  {
304  weight_t min;
305  unsigned pivot = dimension;
306  for (unsigned i = begin; i < dimension; ++i)
307  if (!ws_.is_zero(v[permutation[i]])
308  && (pivot == dimension
309  || ws_.less(norm(v[permutation[i]]), min)))
310  {
311  pivot = i;
312  min = norm(v[permutation[i]]);
313  }
314  return pivot;
315  }
316 
317  // End of Q/R specializations.
318 
319 
320  // Specialization for Z.
321 
322  // Gcd function that also computes the Bezout coefficients.
323  // Used in the z reduction.
324  static z_weight_t
326  {
327  z_weight_t res = 0;
328  //gcd = ax + by
329  if (y == 0)
330  {
331  a = 1;
332  b = 0;
333  res = x;
334  }
335  else if (x < 0)
336  {
337  res = gcd(-x, y, a, b);
338  a = -a;
339  }
340  else if (y < 0)
341  {
342  res = gcd(x, -y, a, b);
343  b = -b;
344  }
345  else if (x < y)
346  res = gcd(y, x, b, a);
347  else
348  {
349  z_weight_t z = x % y; // z= x- (x/y)*y;
350  res = gcd(y, z, b, a);
351  //res=by+az = (b-a(x/y)) y + ax
352  b -= a * (x / y);
353  }
354  assert(res == a * x + b * y);
355  return res;
356  }
357 
358  /*
359  gcd = a.vbasis[pivot] + b.current[pivot]
360  current[pivot] is made zero with a unimodular linear transformation
361  This also modifies the basis vector
362  [ vbasis ] := [ a b ] . [ vbasis ]
363  [ current ] [-current[pivot]/gcd vbasis[pivot]/gcd] [ current ]
364  */
365  void z_reduce_vector(vector_t& vbasis, vector_t& current,
366  unsigned nb, unsigned* permutation)
367  {
368  unsigned pivot = permutation[nb]; //pivot of vector vbasis
369  if (ws_.is_zero(current[pivot]))
370  return;
371  weight_t bp = vbasis[pivot];
372  weight_t cp = current[pivot];
373  weight_t a,b;
374  weight_t g = gcd(bp, cp, a, b);
375  bp /= g;
376  cp /= g;
377  for (unsigned i = nb; i < dimension; ++i)
378  {
379  weight_t tmp = current[permutation[i]];
380  current[permutation[i]] = bp*tmp - cp*vbasis[permutation[i]];
381  vbasis[permutation[i]] = a*vbasis[permutation[i]] + b*tmp;
382  }
383  }
384 
385  void z_vector_in_new_basis(std::vector<vector_t>& basis,
386  vector_t& current, vector_t& new_vector,
387  unsigned* permutation)
388  {
389  for (unsigned b = 0; b < basis.size(); ++b)
390  {
391  vector_t& vbasis = basis[b];
392  unsigned pivot = permutation[b]; //pivot of vector vbasis
393  new_vector[b] = current[pivot] / vbasis[pivot];
394  if (!ws_.is_zero(new_vector[b]))
395  {
396  current[pivot] = ws_.zero();
397  for (unsigned i = b+1; i < dimension; ++i)
398  current[permutation[i]]
399  -= new_vector[b] * vbasis[permutation[i]];
400  }
401  }
402  }
403  // End of Z specializations.
404 
405  /* Generic subroutines.
406  These methods are written for any (skew) field.
407  Some are specialized for Q and R for stability issues.
408  Some are specialized for Z which is an Euclidean domain.
409  */
410 
413  unsigned find_pivot(const vector_t& v, unsigned begin,
414  unsigned* permutation)
415  {
416  for (unsigned i = begin; i < dimension; ++i)
417  if (!ws_.is_zero(v[permutation[i]]))
418  return i;
419  return dimension;
420  }
421 
431  vector_t& current, unsigned b,
432  unsigned* permutation)
433  {
434  unsigned pivot = permutation[b]; //pivot of vector vbasis
435  weight_t ratio = current[pivot];// vbasis[pivot] is one
436  if (ws_.is_zero(ratio))
437  return ratio;
438  // This is safer than current[p] = current[p]-ratio*vbasis[p];
439  current[pivot] = ws_.zero();
440  for (unsigned i = b+1; i < dimension; ++i)
441  current[permutation[i]]
442  = ws_.sub(current[permutation[i]],
443  ws_.mul(ratio, vbasis[permutation[i]]));
444  return ratio;
445  }
446 
448  void normalisation_vector(vector_t& v, unsigned pivot,
449  unsigned* permutation)
450  {
451  weight_t k = v[permutation[pivot]];
452  if (!ws_.is_one(k))
453  {
454  v[permutation[pivot]] = ws_.one();
455  for (unsigned r = pivot + 1; r < dimension; ++r)
456  v[permutation[r]] = ws_.rdivide(v[permutation[r]], k);
457  }
458  }
459 
462  void bottom_up_reduction(std::vector<vector_t>& basis,
463  unsigned* permutation)
464  {
465  for (unsigned b = basis.size()-1; 0 < b; --b)
466  for (unsigned c = 0; c < b; ++c)
467  reduce_vector(basis[b], basis[c], b, permutation);
468  }
469 
471  void vector_in_new_basis(std::vector<vector_t>& basis,
472  vector_t& current, vector_t& new_vector,
473  unsigned* permutation)
474  {
475  for (unsigned b = 0; b < basis.size(); ++b)
476  new_vector[b] = reduce_vector(basis[b], current, b, permutation);
477  }
478 
486  public:
488  {
489  // Used to select the proper overload depending on weightset_t.
490  using type_t = select<weightset_t>;
491 
493  // The basis is a list of vectors, each vector is associated with
494  // a state of the output
495  std::vector<vector_t> basis;
496  // The permutation array corresponds to a permutation of the indices
497  // (i.e. the columns of the matrices) such that permtuation[k]
498  // is the pivot of the k-th vector of the basis.
499  unsigned permutation[dimension];
500  for (unsigned i = 0; i < dimension; ++i)
501  permutation[i] = i;
502  // If the initial vector is null, the function immediatly returns
503 
504  // A non zero entry is chosen as pivot
505  unsigned pivot = type_t::find_pivot(this, init, 0, permutation);
506  if (pivot == dimension) //all components of init are 0
507  return res_;
508  // The pivot of the first basis vector is permutation[0];
509  permutation[0] = pivot;
510  permutation[pivot] = 0;
511  // The initial vector is the first element of the new basis
512  // (up to the normalisation w.r.t the pivot)
513  vector_t first(init);
514  type_t::normalisation_vector(this, first, 0, permutation);
515  basis.push_back(first);
516  // To each vector of the basis, all the successor vectors are
517  // computed, reduced to respect to the basis, and finally, if
518  // linearly independant, pushed at the end of the basis
519  // itself.
520  for (unsigned nb = 0; nb < basis.size(); ++nb)
521  // All the vectors basis[nb].mu(a) are processed
522  for (auto mu : letter_matrix_set) //mu is a pair (letter,matrix)
523  {
524  vector_t current(dimension);
525  product_vector_matrix(basis[nb], mu.second, current);
526  //reduction of current w.r.t each basis vector;
527  for (unsigned b = 0; b < basis.size(); ++b)
528  type_t::reduce_vector(this, basis[b],
529  current, b, permutation);
530  // After reduction, we put current in the basis if it is
531  // not null and we search for the pivot of current.
532  pivot = type_t::find_pivot(this, current, basis.size(),
533  permutation);
534  if (pivot != dimension) //otherwise, current is null
535  {
536  if (pivot != basis.size())
537  std::swap(permutation[pivot], permutation[basis.size()]);
538  type_t::normalisation_vector(this, current,
539  basis.size(), permutation);
540  basis.push_back(current);
541  }
542  }
543 
544  // now, we use each vector to reduce the preceding vectors in
545  // the basis. If weightset=Z we do not do it.
546  type_t::bottom_up_reduction(this, basis, permutation);
547 
548  // Construction of the output automaton
549  // 1. States
550  std::vector<output_state_t> states(basis.size());
551  for (unsigned b = 0; b < basis.size(); ++b)
552  states[b] = res_->new_state();
553  // 2. Initial vector
554  vector_t vect_new_basis(basis.size());
555  type_t::vector_in_new_basis(this, basis, init,
556  vect_new_basis, permutation);
557  for (unsigned b = 0; b < basis.size(); ++b)
558  res_->set_initial(states[b], vect_new_basis[b]);
559  // 3. Each vector of the basis is a state; computation of the
560  // final function and the successor function
561  for (unsigned v = 0; v < basis.size(); ++v)
562  {
563  weight_t k = scalar_product(basis[v],final);
564  if(!ws_.is_zero(k))
565  res_->set_final(states[v],k);
566  for (auto mu : letter_matrix_set)
567  {
568  // mu is a pair (letter,matrix).
569  vector_t current(dimension);
570  product_vector_matrix(basis[v], mu.second, current);
571  type_t::vector_in_new_basis(this, basis, current,
572  vect_new_basis, permutation);
573  for (unsigned b = 0; b < basis.size(); ++b)
574  res_->new_transition(states[v], states[b],
575  mu.first, vect_new_basis[b]);
576  }
577  }
578  return res_;
579  }
580 
581  private:
583  const weightset_t_of<automaton_t> ws_ = *input_->weightset();
584 
586 
587  // Linear representation of the input.
588  unsigned dimension;
590  vector_t final;
592  };
593 
594  }
595 
596  template <Automaton Aut>
597  auto
598  left_reduce(const Aut& input)
599  -> decltype(copy(input))
600  {
602  return left_reduce();
603  }
604 
605 
606  template <Automaton Aut>
607  auto
608  reduce(const Aut& input)
609  -> decltype(copy(input))
610  {
611  return left_reduce(transpose(left_reduce(transpose(input))));
612  }
613 
614  namespace dyn
615  {
616  namespace detail
617  {
619  template <Automaton Aut>
620  automaton
621  reduce(const automaton& aut)
622  {
623  const auto& a = aut->as<Aut>();
624  return reduce(a);
625  }
626  }
627  }
628 }
void z_vector_in_new_basis(std::vector< vector_t > &basis, vector_t &current, vector_t &new_vector, unsigned *permutation)
Definition: reduce.hh:385
auto transitions(const Aut &aut) -> decltype(all_transitions(aut, is_special_t< Aut >
All the transition indexes between visible states.
Definition: automaton.hh:247
typename context_t::weightset_t weightset_t
Definition: reduce.hh:196
return res
Definition: multiply.hh:398
static void vector_in_new_basis(Reduc *that, Basis &basis, Vector &current, Vector &new_vector, unsigned *permutation)
Definition: reduce.hh:180
static void reduce_vector(Reduc *that, Vector &vbasis, Vector &current, unsigned b, unsigned *permutation)
Definition: reduce.hh:96
void vector_in_new_basis(std::vector< vector_t > &basis, vector_t &current, vector_t &new_vector, unsigned *permutation)
Compute the coordinate of a vector in the new basis.
Definition: reduce.hh:471
unsigned find_pivot(const vector_t &v, unsigned begin, unsigned *permutation)
Return the first (w.r.t the column permutation) non zero element as pivot.
Definition: reduce.hh:413
weight_t scalar_product(const vector_t &v, const vector_t &w)
Computes the scalar product of two vectors.
Definition: reduce.hh:258
unsigned find_pivot_by_norm(const vector_t &v, unsigned begin, unsigned *permutation)
Definition: reduce.hh:301
static weight_t norm(const z_weight_t &w)
Norm for integers.
Definition: reduce.hh:294
std::vector< weight_t > vector_t
Definition: reduce.hh:202
auto final_transitions(const Aut &aut) -> decltype(aut->all_in(aut->post()))
Indexes of transitions from (visible) final states.
Definition: automaton.hh:177
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
type_t
The possible types of expressions.
Definition: fwd.hh:39
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
weightset_mixin< detail::b_impl > b
Definition: fwd.hh:48
output_automaton_t operator()()
Core algorithm This algorithm computes a basis of I.mu(w).
Definition: reduce.hh:487
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
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
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
label_t_of< automaton_t > label_t
Definition: reduce.hh:198
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
Definition: automaton.hh:166
std::vector< std::map< std::size_t, weight_t > > matrix_t
Definition: reduce.hh:203
return exp min
Definition: multiply.hh:361
Definition: a-star.hh:8
std::map< label_t, matrix_t > matrix_set_t
Definition: reduce.hh:204
left_reductioner(const automaton_t &input)
Definition: reduce.hh:207
static void vector_in_new_basis(Reduc *that, Basis &basis, Vector &current, Vector &new_vector, unsigned *permutation)
Definition: reduce.hh:119
static void normalisation_vector(Reduc *, Vector &, unsigned, unsigned *)
Definition: reduce.hh:171
static weight_t norm(const r_weight_t &w)
Norm for real numbers; a "stable" pivot should minimize this norm.
Definition: reduce.hh:288
static void reduce_vector(Reduc *that, Vector &vbasis, Vector &current, unsigned b, unsigned *permutation)
Definition: reduce.hh:164
fresh_automaton_t_of< automaton_t > output_automaton_t
Definition: reduce.hh:197
void z_reduce_vector(vector_t &vbasis, vector_t &current, unsigned nb, unsigned *permutation)
Definition: reduce.hh:365
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
vcsn::detail::r_impl::value_t r_weight_t
Definition: reduce.hh:270
A dyn automaton.
Definition: automaton.hh:17
void product_vector_matrix(const vector_t &v, const matrix_t &m, vector_t &res)
Computes the product of a row vector with a matrix.
Definition: reduce.hh:245
const weightset_t_of< automaton_t > ws_
Definition: reduce.hh:583
static unsigned find_pivot(Reduc *that, const Vector &v, unsigned begin, unsigned *permutation)
Definition: reduce.hh:132
static weight_t norm(const q_weight_t &w)
Definition: reduce.hh:282
static void normalisation_vector(Reduc *that, Vector &v, unsigned pivot, unsigned *permutation)
Definition: reduce.hh:104
auto left_reduce(const Aut &input) -> decltype(copy(input))
Definition: reduce.hh:598
vcsn::detail::z_impl::value_t z_weight_t
Specializations for Q and R.
Definition: reduce.hh:268
auto reduce(const Aut &input) -> decltype(copy(input))
Definition: reduce.hh:608
state_t_of< automaton_t > state_t
Definition: reduce.hh:199
void linear_representation()
Create the linear representation of the input.
Definition: reduce.hh:213
weight_t reduce_vector(vector_t &vbasis, vector_t &current, unsigned b, unsigned *permutation)
Reduce a vector w.r.t.
Definition: reduce.hh:430
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
state_t_of< output_automaton_t > output_state_t
Definition: reduce.hh:200
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
Definition: copy.hh:322
output_automaton_t res_
Definition: reduce.hh:585
automaton reduce(const automaton &aut)
Bridge.
Definition: reduce.hh:621
double value_t
Definition: r.hh:41
void normalisation_vector(vector_t &v, unsigned pivot, unsigned *permutation)
Normalize the basis vector such that its pivot is equal to 1.
Definition: reduce.hh:448
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
matrix_set_t letter_matrix_set
Definition: reduce.hh:591
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
void bottom_up_reduction(std::vector< vector_t > &basis, unsigned *permutation)
Apply reduction to vectors of the basis to maximize the number of zeros.
Definition: reduce.hh:462
static unsigned find_pivot(Reduc *that, const Vector &v, unsigned begin, unsigned *permutation)
Definition: reduce.hh:144
typename context_t::weight_t weight_t
Definition: reduce.hh:201
static z_weight_t gcd(z_weight_t x, z_weight_t y, z_weight_t &a, z_weight_t &b)
Definition: reduce.hh:325
context_t_of< automaton_t > context_t
Definition: reduce.hh:195
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253
static void bottom_up_reduction(Reduc *, Basis &, unsigned *)
Definition: reduce.hh:175
static void bottom_up_reduction(Reduc *that, Basis &basis, unsigned *permutation)
Definition: reduce.hh:112
static unsigned find_pivot(Reduc *that, const Vector &v, unsigned begin, unsigned *permutation)
Definition: reduce.hh:88
static unsigned find_pivot(Reduc *that, const Vector &v, unsigned begin, unsigned *permutation)
Definition: reduce.hh:156