automaton.reduce
Compute an equivalent automaton with a minimal number of states.
Preconditions:
its labelset is free
its weightset is a division ring or .
Postconditions:
the result is equivalent to the input automaton
the result is both accessible and co-accessible
Caveats:
The reduction algorithm may well produce an automaton which will look more 'complicated' than the original one, especially when the latter is already of minimal dimension. See examples in below.
The computation of reduced representations implies the exact resolution of linear systems of equations which becomes problematic when the dimension of the systems grows.
See also:
Examples
In
To be contrasted with the results from automaton.minimize:
In
The same automaton, but on , gives:
Caveats
In the result may be suprising. For instance:
The result is not canonical. Moreover, in the algorithm is not idempotent. In fields, the implementation ensures that the reduction of reduced automaton results in an isomorphic automaton.
Algorithm
The core of the algorithm is the left-reduction procedure.
The reduction algorithm of an automaton is left-reduction transpose left-reduction transpose ().
The left-reduction algorithm deals with weighted sets of states, seen as vectors of a vector space with the same dimension as the automaton. It computes greedily a basis of the smallest subspace which contains every accessible weighted set of states.
For efficiency, the basis is scaled, initialized with the initial vector.
Each time a vector is added to the bases, for each letter, a new candidate is built as the successor of the vector by the letter.
Every candidate is reduced with respect to the basis. If the result is not null, the new vector is added to the basis; the pivot of this vector is chosen w.r.t. heuristics for increase numeric stability, and, in case of fields, the vector is normalized in such a way that the pivot equals 1.
In , the reduction of a new vector w.r.t. the basis may modify the basis: let be a vector of the basis with pivot , a new vector, and let and be such that ; then $$ \left[\right]
\left[\right] \left[\right] $$
In fields, once the scaled basis is built, a "bottom-up" procedure is applied to make more entries of the vector of the basis equal to 0. If the input automaton is reduced, the resulting basis is then the canonical basis.
Finally, an automaton is built where each state is a vector of the basis.