We consider the family of all the Cellular Automata (CA) sharing the same local rule but have different memory. This family contains also all the CA with memory m ≤ 0 (one-sided CA) which can act both on A ℤand on A ℕ. We study several set theoretical and topological properties for these classes. In particular we investigate if the properties of a given CA are preserved when we consider the CA obtained by changing the memory of the original one (shifting operation). Furthermore we focus our attention to the one-sided CA acting on A ℤ starting from the one-sided CA acting on A ℕ and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity Density of the Periodic Orbits (DPO)] is equivalent to the conjecture [Topological Mixing DPO]

Acerbi, L., Formenti, E., Dennunzio, A. (2007). Shifting and lifting of cellular automata. In COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS (pp.1-10). Springer [10.1007/978-3-540-73001-9].

Shifting and lifting of cellular automata

Dennunzio, A
2007

Abstract

We consider the family of all the Cellular Automata (CA) sharing the same local rule but have different memory. This family contains also all the CA with memory m ≤ 0 (one-sided CA) which can act both on A ℤand on A ℕ. We study several set theoretical and topological properties for these classes. In particular we investigate if the properties of a given CA are preserved when we consider the CA obtained by changing the memory of the original one (shifting operation). Furthermore we focus our attention to the one-sided CA acting on A ℤ starting from the one-sided CA acting on A ℕ and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity Density of the Periodic Orbits (DPO)] is equivalent to the conjecture [Topological Mixing DPO]
paper
cellular automata, deterministic chaos, discrete time dynamical systems, topological dynamics
English
Conference on Computability in Europe (CiE 2007) JUN 18-23
2007
Cooper, SB; Lowe, B; Sorbi, A
COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS
978-3-540-73000-2
2007
4497
1
10
none
Acerbi, L., Formenti, E., Dennunzio, A. (2007). Shifting and lifting of cellular automata. In COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS (pp.1-10). Springer [10.1007/978-3-540-73001-9].
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/14806
Citazioni
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 11
Social impact