Geodesic
Cascade connections and triangular products of linear automata
Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 7, pp. 175-186
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{FPM_2012_17_7_a9,
     author = {B. Plotkin and T. Plotkin},
     title = {Cascade connections and triangular products of linear automata},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {175--186},
     year = {2012},
     volume = {17},
     number = {7},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2012_17_7_a9/}
}
TY  - JOUR
AU  - B. Plotkin
AU  - T. Plotkin
TI  - Cascade connections and triangular products of linear automata
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2012
SP  - 175
EP  - 186
VL  - 17
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/FPM_2012_17_7_a9/
LA  - ru
ID  - FPM_2012_17_7_a9
ER  - 
%0 Journal Article
%A B. Plotkin
%A T. Plotkin
%T Cascade connections and triangular products of linear automata
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2012
%P 175-186
%V 17
%N 7
%U http://geodesic.mathdoc.fr/item/FPM_2012_17_7_a9/
%G ru
%F FPM_2012_17_7_a9
B. Plotkin; T. Plotkin. Cascade connections and triangular products of linear automata. Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 7, pp. 175-186. http://geodesic.mathdoc.fr/item/FPM_2012_17_7_a9/

[1] Arbib M. A. (ed.), Algebraic Theory of Machines, Languages, and Semigroups, Academic Press, New York, 1968 | MR | Zbl

[2] Eilenberg S., Automata, Languages and Machines, Academic Press, New York, 1976 | MR | Zbl

[3] Gecseg F., Products of Automata, EATCS Monogr. on TCS, Springer, Berlin, 1986 | MR | Zbl

[4] Gecseg F., Peak I., Algebraic Theory of Automata, Akademiai Kiado, 1972 | MR

[5] Holcombe M., Algebraic Automata Theory, Cambridge Univ. Press, Cambridge, 1982 | MR | Zbl

[6] Ito M., Algebraic Theory of Automata and Languages, World Scientific, 2004 | MR

[7] Kambites M., “On the Krohn–Rhodes complexity of semigroups of upper triangular matrices”, Int. J. Algebra Comput., 17:1 (2007), 187–201 | DOI | MR | Zbl

[8] Kambites M., Steinberg B., “Wreath product decompositions for triangular matrix semigroups”, Proc. Semigroups and Languages, Lisbon, 2005, 129–144 | MR

[9] Krohn K., Rhodes J., “Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines”, Trans. Am. Math. Soc., 116 (1965), 450–464 | DOI | MR | Zbl

[10] Krohn K., Rhodes J., “Complexity of finite semigroups”, Ann. Math., 2:88 (1968), 128–160 | DOI | MR | Zbl

[11] Krohn K., Rhodes J., Tilson B., “Lectures on finite semigroups”, Algebraic Theory of Machines, Languages and Semigroups, Academic Press, New York, 1968 | MR

[12] Plotkin B., Greenglaz L., Gvaramija A., Algebraic Structures in Automata and Databases Theory, World Scientific, Singapore, 1992 | MR | Zbl

[13] Plotkin B., Plotkin T., “An algebraic approach to knowledge bases informational equivalence”, Acta Appl. Math., 89 (2005), 109–134 | DOI | MR | Zbl

[14] Plotkin B. I., Vovsi S. M., Varieties of Representations of Groups, Zinatne, 1983 | MR | Zbl

[15] Rhodes J., Steinberg B., The $q$-Theory of Finite Semigroups, Monograph (to appear)

[16] Vovsi S. M., Triangular Products of Group Representations and Their Applications, Progress Math., 17, Birkhäuser, 1981 | MR | Zbl