首页 | 本学科首页   官方微博 | 高级检索  
     


Sand automata as cellular automata
Authors:Alberto Dennunzio  Pierre Guillon  Benoît Masson  
Affiliation:1. Università degli studi di Milano-Bicocca, Dipartimento di Informatica Sistemistica e Comunicazione, viale Sarca 336, 20126 Milano, Italy;2. Université Paris-Est, Laboratoire d’Informatique de l’Institut Gaspard Monge, UMR CNRS 8049, 5 bd Descartes, 77454 Marne la Vallée Cedex 2, France;3. Laboratoire d’Informatique Fondamentale de Marseille (LIF)-CNRS, Aix-Marseille Université, 39 rue Joliot-Curie, 13453 Marseille Cedex 13, France
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.
Keywords:Sand automata  Cellular automata  Dynamical systems  Nilpotency  Undecidability
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号