Decidability of Sensitivity and Equicontinuity for Linear Higher-order Cellular Automata

none5siWe study the dynamical behavior of linear higher-order cellular automata (HOCA) over Z_m. In standard cellular automata the global state of the system at time t only depends on the state at time t − 1, while in HOCA it is a function of the states at time t − 1, . . . , t − n, where n ≥ 1 is the memory size. In particular, we provide easy-to-check necessary and sufficient conditions for a linear HOCA over Z_m of memory size n to be sensitive to the initial conditions or equicontinuous. Our characterizations of sensitivity and equicontinuity extend the ones shown in [23] for linear cellular automata (LCA) over Z^n_m in the case n = 1. We also prove that linear HOCA over Z_m of memory size n are indistinguishable from a subclass of LCA over Z^n_m. This enables to decide injectivity and surjectivity for linear HOCA over Z_m of memory size n by means of the decidable characterizations of injectivity and surjectivity provided in [2] and [20] for LCA over Z^n_m.noneAlberto Dennunzio, Enrico Formenti, Luca Manzoni, Luciano Margara, Antonio E. PorrecaAlberto Dennunzio, Enrico Formenti, Luca Manzoni, Luciano Margara, Antonio E. Porrec