Composition and decomposition of linear automata. Algebraic view
by
Tatjana Plotkin
Bar Ilan University, Tel Aviv
Coauthors: Boris Plotkin (Hebrew University of Jerusalem)

The talk has a double goal. Looking at the subject from the position of applications of algebra, our goal is to define a new notion of linear automata complexity. Our second goal is to describe the algebraic constructions and ideas which make such a definition possible. With this end we discuss the constructions of wreath product and triangular product of linear automata leading to the composition and decomposition theory for linear automata.

We view an automaton as a structure which equally belongs to algebra and to applications. Algebraic methods and results work well in various Computer Science problems. The feedback to this relation stimulates development of new areas in algebra itself.

We consider three constructions: wreath product of pure automata, triangular product of linear automata and wreath product of a linear automaton with a pure one leading to a linear automaton. The wreath product construction is a core of well known Krohn-Rhodes theory. We notice that wreath product is a universal object in the category of cascade connections of two given automata. Hence, every pure automata cascade connection can be viewed as a sub-automaton of the wreath product. We consider the similar theorem for linear automata where triangular products play the role of wreath products. In particular, triangular product of linear automata is a universal object in the category of cascade connections of linear automata.

The decomposition theorem for linear automata uses all three constructions. It allows us to define complexity of a linear automaton. We prove that every linear automaton over a field is a divisor of the triangular product of its divisors. The factors of this decomposition are indecomposable. However they can be decomposed further using wreath product of a linear automaton with a pure one. We define complexity of a linear automaton counting the indecomposable factors.

Date received: February 24, 2008