Higher-order cellular automata (HOCA) are a variant of cellular automata (CA) used in many applications (ranging, for instance, from the design of secret sharing schemes to data compression and image processing), and in which the global state of the system at time t depends not only on the state at time t−1, as in the original model, but also on the states at time t−2, …,t−n, where n is the memory size of the HOCA. We provide decidable characterizations of two important dynamical properties, namely, sensitivity to the initial conditions and equicontinuity, for linear HOCA over the alphabet Z_m. These characterizations have an impact in applications since the involved linear HOCA are usually required to exhibit a chaotic or stable behaviour. Moreover, they extend the ones shown in [28] for linear CA (LCA) over the alphabet Z_m^n in the case n=1. We also show that linear HOCA of memory size n over Z_m form a class that is indistinguishable from a specific subclass of LCA over Z_m^n. This enables to decide injectivity and surjectivity for linear HOCA of memory size n over Z_m using the decidable characterization provided in [2] and [25] for injectivity and surjectivity of LCA over Z_m^n. Finally, we prove an equivalence between LCA over Z_m^n and an important class of non-uniform CA, another variant of CA used in many applications.

On the dynamical behaviour of linear higher-order cellular automata and its decidability

Manzoni Luca;
2019-01-01

Abstract

Higher-order cellular automata (HOCA) are a variant of cellular automata (CA) used in many applications (ranging, for instance, from the design of secret sharing schemes to data compression and image processing), and in which the global state of the system at time t depends not only on the state at time t−1, as in the original model, but also on the states at time t−2, …,t−n, where n is the memory size of the HOCA. We provide decidable characterizations of two important dynamical properties, namely, sensitivity to the initial conditions and equicontinuity, for linear HOCA over the alphabet Z_m. These characterizations have an impact in applications since the involved linear HOCA are usually required to exhibit a chaotic or stable behaviour. Moreover, they extend the ones shown in [28] for linear CA (LCA) over the alphabet Z_m^n in the case n=1. We also show that linear HOCA of memory size n over Z_m form a class that is indistinguishable from a specific subclass of LCA over Z_m^n. This enables to decide injectivity and surjectivity for linear HOCA of memory size n over Z_m using the decidable characterization provided in [2] and [25] for injectivity and surjectivity of LCA over Z_m^n. Finally, we prove an equivalence between LCA over Z_m^n and an important class of non-uniform CA, another variant of CA used in many applications.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0020025519301318-main.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 740.53 kB
Formato Adobe PDF
740.53 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
On the dynamical behaviour of linear higher-order cellular automata and its decidability.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Digital Rights Management non definito
Dimensione 214.69 kB
Formato Adobe PDF
214.69 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/11368/2947814
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 19
social impact