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

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.
Language and Automata Theory and Applications - LATA 2019 
95
107
LECTURE NOTES IN COMPUTER SCIENCE
Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Luciano Margara, Antonio E. Porreca
File in questo prodotto:
Eventuali allegati, non sono esposti

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: http://hdl.handle.net/11585/655381
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact