We introduce an algebraic approach for the analysis and composition of finite, discrete-time dynamical systems based on the category-theoretical operations of product and sum (coproduct). This allows us to define a semiring structure over the set of dynamical systems (modulo isomorphism) and, consequently, to express many decomposition problems in terms of polynomial equations. We prove that these equations are, in general, algorithmically unsolvable, but we identify a solvable subclass. Finally, we describe an implementation of the semiring operations for the case of finite cellular automata.

Dennunzio, A., Dorigatti, V., Formenti, E., Manzoni, L., Porreca, A. (2018). Polynomial Equations over Finite, Discrete-Time Dynamical Systems. In Cellular Automata (pp.298-306). Springer Verlag [10.1007/978-3-319-99813-8_27].

Polynomial Equations over Finite, Discrete-Time Dynamical Systems

Dennunzio, A;DORIGATTI, VALENTINA;Manzoni, L
;
Porreca, AE
2018

Abstract

We introduce an algebraic approach for the analysis and composition of finite, discrete-time dynamical systems based on the category-theoretical operations of product and sum (coproduct). This allows us to define a semiring structure over the set of dynamical systems (modulo isomorphism) and, consequently, to express many decomposition problems in terms of polynomial equations. We prove that these equations are, in general, algorithmically unsolvable, but we identify a solvable subclass. Finally, we describe an implementation of the semiring operations for the case of finite cellular automata.
paper
Theoretical Computer Science; Computer Science (all)
English
International Conference on Cellular Automata for Research and Industry, ACRI 2018
2018
Cellular Automata
9783319998121
2018
11115
298
306
none
Dennunzio, A., Dorigatti, V., Formenti, E., Manzoni, L., Porreca, A. (2018). Polynomial Equations over Finite, Discrete-Time Dynamical Systems. In Cellular Automata (pp.298-306). Springer Verlag [10.1007/978-3-319-99813-8_27].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/219974
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
Social impact