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.
Enrico Formenti has been partially supported by PACA APEX FRI project. Luca Manzoni was partially supported by “Premio giovani talenti 2017” of Università degli Studi di Milano-Bicocca and Accademia dei Lincei.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
While the existence of integer roots of a polynomial in \(\mathbb {Z}[X]\) is undecidable, the existence of roots in the larger ring of real numbers is decidable, and the problem becomes even trivial for complex roots (due to the fundamental theorem of algebra).
References
Colbourn, C.J.: On testing isomorphism of permutation graphs. Networks 11(1), 13–21 (1981)
Hebisch, U., Weinert, H.J.: Semirings: Algebraic Theory and Applications in Computer Science. World Scientific, Singapore (1998)
Lawvere, F.W., Schanuel, S.H.: Conceptual Mathematics: A First Introduction to Categories, 2nd edn. Cambridge University Press, Cambridge (2009)
Matiyasevich, Y.: Hilbert’s Tenth Problem. MIT Press, Cambridge (1993)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Dennunzio, A., Dorigatti, V., Formenti, E., Manzoni, L., Porreca, A.E. (2018). Polynomial Equations over Finite, Discrete-Time Dynamical Systems. In: Mauri, G., El Yacoubi, S., Dennunzio, A., Nishinari, K., Manzoni, L. (eds) Cellular Automata. ACRI 2018. Lecture Notes in Computer Science(), vol 11115. Springer, Cham. https://doi.org/10.1007/978-3-319-99813-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-99813-8_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99812-1
Online ISBN: 978-3-319-99813-8
eBook Packages: Computer ScienceComputer Science (R0)