We 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.
Decidability of Sensitivity and Equicontinuity for Linear Higher-order Cellular Automata / Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Luciano Margara, Antonio E. Porreca. - STAMPA. - 11417:(2019), pp. 95-107. (Intervento presentato al convegno Language and Automata Theory and Applications - LATA 2019 tenutosi a Saint Petersburg, Russia nel March 26-29, 2019) [10.1007/978-3-030-13435-8_7].
Decidability of Sensitivity and Equicontinuity for Linear Higher-order Cellular Automata
Luciano Margara;
2019
Abstract
We 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
