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
Complete list of metadatas

Cited literature [50 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102505
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 1:54:39 PM
Last modification on : Friday, April 19, 2019 - 1:38:16 AM

File

RR2005-29.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102505, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

6