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

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

Manzoni Luca;
2019-01-01

Abstract

We study the dynamical behavior of linear higher-order cellular automata (HOCA) over ℤ_ . In standard cellular automata the global state of the system at time t only depends on the state at time −1, while in HOCA it is a function of the states at time −1 , ..., −, where ≥1 is the memory size. In particular, we provide easy-to-check necessary and sufficient conditions for a linear HOCA over ℤ_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 ℤ^_ in the case =1. We also prove that linear HOCA over ℤ_of memory size n are indistinguishable from a subclass of LCA over ℤ^_. This enables to decide injectivity and surjectivity for linear HOCA over ℤ_ of memory size n by means of the decidable characterizations of injectivity and surjectivity provided in [2] and [20] for LCA over ℤ^_.
2019
978-3-030-13434-1
978-3-030-13435-8
https://www.springer.com/series/558
File in questo prodotto:
File Dimensione Formato  
(Lecture Notes in Computer Science 11417)1.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 4.53 MB
Formato Adobe PDF
4.53 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/2948002
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact