automaton.reduce

Compute an equivalent automaton with a minimal number of states.

Preconditions:

  • its labelset is free
  • its weightset is a division ring or $\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 $\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

In [1]:
import vcsn

In $\mathbb{Q}$

In [2]:
c = vcsn.context('lal_char(ab), q')
a = c.expression('<2>(<3>a+<5>b+<7>a)*<11>', 'associative').standard()
a
Out[2]:
%3 I0 0 0 I0->0 F0 F1 F3 F4 0->F0 ⟨22⟩ 1 1 0->1 ⟨6⟩a 3 3 0->3 ⟨10⟩b 4 4 0->4 ⟨14⟩a 1->F1 ⟨11⟩ 1->1 ⟨3⟩a 1->3 ⟨5⟩b 1->4 ⟨7⟩a 3->F3 ⟨11⟩ 3->1 ⟨3⟩a 3->3 ⟨5⟩b 3->4 ⟨7⟩a 4->F4 ⟨11⟩ 4->1 ⟨3⟩a 4->3 ⟨5⟩b 4->4 ⟨7⟩a
In [3]:
a.reduce()
Out[3]:
%3 I0 0 0 I0->0 ⟨2⟩ F0 0->F0 ⟨11⟩ 0->0 ⟨10⟩a, ⟨5⟩b

To be contrasted with the results from automaton.minimize:

In [4]:
a.minimize()
Out[4]:
%3 I0 0 0 I0->0 F0 F1 0->F0 ⟨22⟩ 1 1, 3, 4 0->1 ⟨20⟩a, ⟨10⟩b 1->F1 ⟨11⟩ 1->1 ⟨10⟩a, ⟨5⟩b

In $\mathbb{Z}$

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

In [5]:
c = vcsn.context('lal_char(ab), z')
a = c.expression('<2>(<3>a+<5>b+<7>a)*<11>', 'associative').standard()
a.reduce()
Out[5]:
%3 I0 0 0 I0->0 F0 0->F0 ⟨22⟩ 0->0 ⟨10⟩a, ⟨5⟩b

Caveats

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

In [6]:
%%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 -> $
%3 I0 0 0 I0->0 F1 0->0 a, b 1 1 0->1 b 2 2 0->2 ⟨2⟩b 1->F1 1->1 ⟨4⟩a, ⟨4⟩b 2->1 ⟨2⟩b 2->2 ⟨2⟩a, ⟨2⟩b
In [7]:
a.reduce()
Out[7]:
%3 I0 0 0 I0->0 F1 0->0 a, ⟨9⟩b 1 1 0->1 b 1->F1 1->0 ⟨8⟩a, ⟨-56⟩b 1->1 ⟨4⟩a 2 2 1->2 ⟨-1⟩a, ⟨-3⟩b 2->0 ⟨16⟩a, ⟨-112⟩b 2->1 ⟨-8⟩b 2->2 ⟨2⟩a, ⟨-2⟩b
In [8]:
a = vcsn.context('lal_char(ab), z').expression('[ab]*b(<2>[ab])*').automaton()
a
Out[8]:
%3 I0 0 0 I0->0 F1 0->0 a, b 1 1 0->1 b 1->F1 1->1 ⟨2⟩a, ⟨2⟩b
In [9]:
a.reduce()
Out[9]:
%3 I0 0 0 I0->0 I1 1 1 I1->1 ⟨-1⟩ F0 F1 0->F0 0->0 a, b 0->1 a, ⟨2⟩b 1->F1 1->1 ⟨2⟩a, ⟨2⟩b

The result is not canonical. Moreover, in $\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 $\mathcal{A}$ is left-reduction $\circ$ transpose $\circ$ left-reduction $\circ$ transpose ($\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 $\mathbb{Z}$, the reduction of a new vector w.r.t. the basis may modify the basis: let $b$ be a vector of the basis with pivot $b_i$, $v$ a new vector, and let $\alpha$ and $\beta$ be such that $\alpha b_i+ \beta v_i=\mathsf{gcd}(b_i,v_i)$; then $$

\left[\begin{array}{c}b'\v'\end{array}\right]

\left[\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[\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.