We prove that important properties describing complex behaviours as ergodicity, chaos, topological transitivity, and topological mixing, are decidable for one-dimensional linear cellular automata (LCA) over (Z/mZ)n (Theorem 6 and Corollary 7), a large and important class of cellular automata (CA) which are able to exhibit the complex behaviours of general CA and are used in applications. In particular, we provide a decidable characterization of ergodicity, which is known to be equivalent to all the above mentioned properties, in terms of the characteristic polynomial of the matrix associated with LCA. We stress that the setting of LCA over (Z/mZ)n with n>1 is more expressive, gives rise to much more complex dynamics, and is more difficult to deal with than the already investigated case n=1. The proof techniques from [23,25] used when n=1 for obtaining decidable characterizations of dynamical and ergodic properties can no longer be exploited when n>1 for achieving the same goal. Indeed, in order to get the decision algorithm (Algorithm 1) we need to prove a non trivial result of abstract algebra (Theorem 5) which is also of interest in its own. We also illustrate the impact of our results in real-world applications concerning the important and growing domain of cryptosystems which are often based on one-dimensional LCA over (Z/mZ)n with n>1. As a matter of facts, since cryptosystems have to satisfy the so-called confusion and diffusion properties (ensured by ergodicity and chaos, respectively, of the involved LCA) Algorithm *1 turns out to be an important tool for building chaotic/ergodic one-dimensional linear CA over (Z/mZ)n and, hence, for improving the existing methods based on them.

Dennunzio, A., Formenti, E., Grinberg, D., Margara, L. (2020). Chaos and ergodicity are decidable for linear cellular automata over (Z/mZ)n. INFORMATION SCIENCES, 539, 136-144 [10.1016/j.ins.2020.05.123].

Chaos and ergodicity are decidable for linear cellular automata over (Z/mZ)n

Dennunzio A.
;
Formenti E.
;
2020

Abstract

We prove that important properties describing complex behaviours as ergodicity, chaos, topological transitivity, and topological mixing, are decidable for one-dimensional linear cellular automata (LCA) over (Z/mZ)n (Theorem 6 and Corollary 7), a large and important class of cellular automata (CA) which are able to exhibit the complex behaviours of general CA and are used in applications. In particular, we provide a decidable characterization of ergodicity, which is known to be equivalent to all the above mentioned properties, in terms of the characteristic polynomial of the matrix associated with LCA. We stress that the setting of LCA over (Z/mZ)n with n>1 is more expressive, gives rise to much more complex dynamics, and is more difficult to deal with than the already investigated case n=1. The proof techniques from [23,25] used when n=1 for obtaining decidable characterizations of dynamical and ergodic properties can no longer be exploited when n>1 for achieving the same goal. Indeed, in order to get the decision algorithm (Algorithm 1) we need to prove a non trivial result of abstract algebra (Theorem 5) which is also of interest in its own. We also illustrate the impact of our results in real-world applications concerning the important and growing domain of cryptosystems which are often based on one-dimensional LCA over (Z/mZ)n with n>1. As a matter of facts, since cryptosystems have to satisfy the so-called confusion and diffusion properties (ensured by ergodicity and chaos, respectively, of the involved LCA) Algorithm *1 turns out to be an important tool for building chaotic/ergodic one-dimensional linear CA over (Z/mZ)n and, hence, for improving the existing methods based on them.
Articolo in rivista - Articolo scientifico
Cellular automata; Complex systems; Decidability; Linear cellular automata; Symbolic dynamics
English
7-giu-2020
2020
539
136
144
reserved
Dennunzio, A., Formenti, E., Grinberg, D., Margara, L. (2020). Chaos and ergodicity are decidable for linear cellular automata over (Z/mZ)n. INFORMATION SCIENCES, 539, 136-144 [10.1016/j.ins.2020.05.123].
File in questo prodotto:
File Dimensione Formato  
Dennunzio-2020-Inf Sci-VoR.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Licenza: Tutti i diritti riservati
Dimensione 365.68 kB
Formato Adobe PDF
365.68 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/295301
Citazioni
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 10
Social impact