We consider the family of all the Cellular Automata (CA) sharing the same local rule but having different memories. This family contains also all CA with memory m ≤ 0 (one-sided CA) which can act both on AZ and on AN. We study several set theoretical and topological properties for these classes. In particular, we investigate whether the properties of a given CA are preserved when considering the CA obtained by changing the memory of the original one (shifting operation). Furthermore, we focus our attention on the one-sided CA acting on AZ, starting from the one-sided CA acting on AN and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity ⇒ Dense Periodic Orbits (DPO)] can be restated in several different (but equivalent) ways. Furthermore, we give some results on properties conserved under the iteration of the CA global map. © 2009 Elsevier B.V. All rights reserved.

Acerbi, L., Dennunzio, A., Formenti, E. (2009). Conservation of some dynamical properties for operations on cellular automata. THEORETICAL COMPUTER SCIENCE, 410, 3685-3693 [10.1016/j.tcs.2009.05.004].

Conservation of some dynamical properties for operations on cellular automata

DENNUNZIO, ALBERTO;
2009

Abstract

We consider the family of all the Cellular Automata (CA) sharing the same local rule but having different memories. This family contains also all CA with memory m ≤ 0 (one-sided CA) which can act both on AZ and on AN. We study several set theoretical and topological properties for these classes. In particular, we investigate whether the properties of a given CA are preserved when considering the CA obtained by changing the memory of the original one (shifting operation). Furthermore, we focus our attention on the one-sided CA acting on AZ, starting from the one-sided CA acting on AN and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity ⇒ Dense Periodic Orbits (DPO)] can be restated in several different (but equivalent) ways. Furthermore, we give some results on properties conserved under the iteration of the CA global map. © 2009 Elsevier B.V. All rights reserved.
Articolo in rivista - Articolo scientifico
cellular automata, symbolic dynamics
English
2009
410
3685
3693
none
Acerbi, L., Dennunzio, A., Formenti, E. (2009). Conservation of some dynamical properties for operations on cellular automata. THEORETICAL COMPUTER SCIENCE, 410, 3685-3693 [10.1016/j.tcs.2009.05.004].
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/14986
Citazioni
  • Scopus 45
  • ???jsp.display-item.citation.isi??? 40
Social impact