  The Krohn-Rhodes complexity theory for pure (without linearity) automata is
well-known. This theory uses an operation of wreath product as a decomposition
tool. The main goal of the paper is to introduce the notion of complexity of
linear automata. This notion is ultimately related with decompositions of
linear automata. The study of these decompositions is the second objective of
the paper. In order to define complexity for linear automata, we have to use
three operations, namely, triangular product of linear automata, wreath product
of pure automata and wreath product of a linear automaton with a pure one which
returns a linear automaton. We define the complexity of a linear automaton as
the minimal number of operations in the decompositions of the automaton into
indecomposable components (atoms). This theory relies on the following
parallelism between wreath and triangular products: both of them are terminal
objects in the categories of cascade connections of automata. The wreath
product is the terminal object in the Krohn-Rhodes theory for pure automata,
while the triangular product provides the terminal object for the cascade
connections of linear automata.
