In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with simple sand automata. We show that the classical definition of nilpotency is not meaningful for sand automata. Then, we introduce the suitable new notion of flattening sand automata. Finally, we prove that this simple dynamical behavior is undecidable. © 2009 Elsevier B.V. All rights reserved.

Dennunzio, A., Guillon, P., & Masson, B. (2009). Sand automata as cellular automata. THEORETICAL COMPUTER SCIENCE, 410, 3962-3974 [10.1016/j.tcs.2009.06.016].

Sand automata as cellular automata

DENNUNZIO, ALBERTO;
2009

Abstract

In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with simple sand automata. We show that the classical definition of nilpotency is not meaningful for sand automata. Then, we introduce the suitable new notion of flattening sand automata. Finally, we prove that this simple dynamical behavior is undecidable. © 2009 Elsevier B.V. All rights reserved.
Articolo in rivista - Articolo scientifico
cellular automata, dynamical systems, nilpotency, sand automata, undecidability
English
3962
3974
Dennunzio, A., Guillon, P., & Masson, B. (2009). Sand automata as cellular automata. THEORETICAL COMPUTER SCIENCE, 410, 3962-3974 [10.1016/j.tcs.2009.06.016].
Dennunzio, A; Guillon, P; Masson, B
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/15006
Citazioni
  • Scopus 27
  • ???jsp.display-item.citation.isi??? 23
Social impact