FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2011/2012, VOLUME 17, NUMBER 7, PAGES 175-186

**Cascade connections and triangular products of linear automata**

B. Plotkin

T. Plotkin

Abstract

View as HTML
View as gif image

In this note, we want to resume attention to the basics of triangular
product of automata construction and to introduce the notion of linear
automata complexity.
It contains three main results.
(1) For any two pure automata we consider the category of their
cascade connections.
It possesses the universal terminal object.
This object is the wreath product of the automata.
Hence, every cascade connection admits a natural embedding into
wreath product of automata.
(2) A similar theory is built for linear automata, where we
also consider the category of cascade connections.
It also has the terminal object.
This object is the triangular product of linear automata.
(3) Triangular products have various applications.
This construction is used in linear automata decomposition theory, in
the definition of complexity of a linear automaton.
We consider a special linear complexity and give the rule for its
calculation.

Location: http://mech.math.msu.su/~fpm/eng/k1112/k117/k11710h.htm

Last modified: May 24, 2013