We study the dynamical behavior of linear higher-order cellular automata (HOCA) over (Formula Presented). In standard cellular automata the global state of the system at time t only depends on the state at time (Formula Presented), while in HOCA it is a function of the states at time (Formula Presented),.., (Formula Presented), where (Formula Presented) is the memory size. In particular, we provide easy-to-check necessary and sufficient conditions for a linear HOCA over (Formula Presented) 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 (Formula Presented) in the case (Formula Presented). We also prove that linear HOCA over (Formula Presented) of memory size n are indistinguishable from a subclass of LCA over (Formula Presented). This enables to decide injectivity and surjectivity for linear HOCA over(Formula Presented) of memory size n by means of the decidable characterizations of injectivity and surjectivity provided in [2] and [20] for LCA over (Formula Presented).

Dennunzio, A., Formenti, E., Manzoni, L., Margara, L., Porreca, A. (2019). Decidability of Sensitivity and Equicontinuity for Linear Higher-Order Cellular Automata. In Language and Automata Theory and Applications : 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings (pp.95-107). Cham : Springer Verlag [10.1007/978-3-030-13435-8_7].

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

Dennunzio, A;Manzoni, L;Porreca, A
2019

Abstract

We study the dynamical behavior of linear higher-order cellular automata (HOCA) over (Formula Presented). In standard cellular automata the global state of the system at time t only depends on the state at time (Formula Presented), while in HOCA it is a function of the states at time (Formula Presented),.., (Formula Presented), where (Formula Presented) is the memory size. In particular, we provide easy-to-check necessary and sufficient conditions for a linear HOCA over (Formula Presented) 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 (Formula Presented) in the case (Formula Presented). We also prove that linear HOCA over (Formula Presented) of memory size n are indistinguishable from a subclass of LCA over (Formula Presented). This enables to decide injectivity and surjectivity for linear HOCA over(Formula Presented) of memory size n by means of the decidable characterizations of injectivity and surjectivity provided in [2] and [20] for LCA over (Formula Presented).
paper
Cellular automata, Higher-order cellular automata, Linear cellular automata, Sensitivity to the initial conditions, Decidability, Discrete dynamical systems
English
Language and Automata Theory and Applications - 13th InternationalConference, LATA 2019
2019
Martín-Vide, C; Okhotin, A; Shapira, D
Language and Automata Theory and Applications : 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings
9783030134341
2019
11417
95
107
https://link.springer.com/chapter/10.1007/978-3-030-13435-8_7
none
Dennunzio, A., Formenti, E., Manzoni, L., Margara, L., Porreca, A. (2019). Decidability of Sensitivity and Equicontinuity for Linear Higher-Order Cellular Automata. In Language and Automata Theory and Applications : 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings (pp.95-107). Cham : Springer Verlag [10.1007/978-3-030-13435-8_7].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/10281/225925
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
Social impact