Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Hiérarchies algébriques de classes d'automates cellulaires

Abstract : Cellular automata are a formal model of locally interacting systems which is very simple but suitable to study complex systems in general. Many classifications have been proposed in the literature, often relying on the observation of dynamics. In a first part, we present more recent approaches of algebraic nature based on notions of sub-systems or embeddings. A second part, which is more technical, is dedicated to new results concerning these algebraic tools. This framework allows us to give formal definitions to several intuitive global notions (e.g., universality, particles) and to derive formal proofs of positive results and, more interestingly, of negative results. More precisely, we show that modifying local rules may be more powerful in some sense than increasing the number of states ; then, we illustrate by the construction of an infinite lattice that dynamical universality is incredibly more powerful than usual computation universality.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [57 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 1:54:39 PM
Last modification on : Wednesday, October 26, 2022 - 8:15:28 AM


Files produced by the author(s)


  • HAL Id : hal-02102505, version 1



Marianne Delorme, Jacques Mazoyer, Guillaume Theyssier. Hiérarchies algébriques de classes d'automates cellulaires. [Rapport de recherche] LIp RR-2005-29, Laboratoire de l'informatique du parallélisme. 2005, 2+49p. ⟨hal-02102505⟩



Record views


Files downloads