On Linear Cellular Automata
Tallinn University of Technology
Abstract:
Cellular automata (CA) are models of parallel computation on regular grids of state machines where a local update rule, whose output depends on the current state of a neighborhood, is applied synchronously at every node: such process determines a global transition function of the space of configurations of the entire grid. This construction has important practical applications and interesting theoretical properties.
If the set of states is a module on a ring R, then the space of configurations with pointwise operations is also an R-module. The case where the global function is an R-module homomorphism is of particular interest for several reasons. On the one hand, some properties which are in general undecidable for generic CA, become decidable for linear CA, provided the grid and set of states satisfy some basic requirements. On the other hand, cryptographic protocols based on linear CA have been proposed, and some dynamical properties which are equivalent to good cryptographic properties have been proven to be decidable, at least under some specific conditions.
In this talk, after an introduction to the classical theory of cellular automata, I will present, among others, some classical results by Sato and an extension by Yukita, then some more recent ones by Dennunzio et al. I will also discuss how all this could be seen under a formalization of CA as coalgebra maps due to Uustalu and me.