Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 45858
Kernel: Python 3

automaton.reduce

Compute an equivalent automaton with a minimal number of states.

Preconditions:

  • its labelset is free

  • its weightset is a division ring or Z\mathbb{Z}.

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 Z\mathbb{Z} 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

import vcsn

In Q\mathbb{Q}

c = vcsn.context('lal_char(ab), q') a = c.expression('<2>(<3>a+<5>b+<7>a)*<11>', 'associative').standard() a
Image in a Jupyter notebook
a.reduce()
Image in a Jupyter notebook

To be contrasted with the results from automaton.minimize:

a.minimize()
Image in a Jupyter notebook

In Z\mathbb{Z}

The same automaton, but on Z\mathbb{Z}, gives:

c = vcsn.context('lal_char(ab), z') a = c.expression('<2>(<3>a+<5>b+<7>a)*<11>', 'associative').standard() a.reduce()
Image in a Jupyter notebook

Caveats

In Z\mathbb{Z} the result may be suprising. For instance:

%%automaton -s a context = "lal_char(abc), z" $ -> 0 0 -> 0 a, b 0 -> 1 b 0 -> 2 <2>b 2 -> 2 <2>a, <2>b 2 -> 1 <2>b 1 -> 1 <4>a, <4>b 1 -> $
Image in a Jupyter notebook
a.reduce()
Image in a Jupyter notebook
a = vcsn.context('lal_char(ab), z').expression('[ab]*b(<2>[ab])*').automaton() a
Image in a Jupyter notebook
a.reduce()
Image in a Jupyter notebook

The result is not canonical. Moreover, in Z\mathbb{Z} 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 A\mathcal{A} is left-reduction \circ transpose \circ left-reduction \circ transpose (A\mathcal{A}).

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 Z\mathbb{Z}, the reduction of a new vector w.r.t. the basis may modify the basis: let bb be a vector of the basis with pivot bib_i, vv a new vector, and let α\alpha and β\beta be such that αbi+βvi=gcd(bi,vi)\alpha b_i+ \beta v_i=\mathsf{gcd}(b_i,v_i); then $$ \left[bv\begin{array}{c}b'\\v'\end{array}\right]

\left[αβvigcd(bi,vi)bigcd(bi,vi)\begin{array}{cc}\alpha & \beta \\-\frac{v_i}{\mathsf{gcd}(b_i,v_i)} & \frac{b_i}{\mathsf{gcd}(b_i,v_i)} \end{array}\right] \left[bv\begin{array}{c}b\\v\end{array}\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.