A K-automaton A over an alphabet A of dimension Q usually written under its matrix form as A=<I,E,T> is more conveniently described for the purpose of the reduction algorithm under its 'representation' form A=<I,µ,T>, where µ is the morphism from A^* into K^{QxQ} defined by

E = \sum_{a\in A} µ(a) a .

If K is a field, A is said to be controllable if the dimension of the vector-space generated by the set of vectors { I.µ(w) | w \in A^* } is Q and A is said to be observable if the dimension of the vector-space generated by the set of vectors { µ(w).T | w \in A^* } is Q. Indeed, A is observable if the transpose of A is controllable.

An automaton A is said to be reduced if it is of minimal dimension among all equivalent automata equivalent to A. The reduction algorithm is then based on the two following results:

Theorem 1 : A is reduced if it is both controllable and observable.

Theorem 2 : Given A= <I,µ,T>, it is possible to compute effectively an automaton A'= <I',µ',T'> which is 'conjugate' (hence equivalent) to A and with the two properties:
• A' is controllable;
• if A is observable, so is A'.

These results, hence the algorithm, may be generalized to skew fields, and to PID (Principal Ideal Domains) such as Z.

The algorithm is due to M. P. Schützenberger, in his paper where he introduced the notion of weighted automata ('On the definition of a family of automata Information & Control 1961'). More details and bibliographical information can be found in 'J. Sakarovitch, Rational and recognisable series, in Handbook of Weighted Automata, Springer, 2009'.