Quick convergence to a fixed point: A note on asynchronous Elementary Cellular Automata

Nazim Fatès 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : This note describes a small step in the analysis of the fully asynchronous cellular automata (i.e., the cells are updated uniformly at random at each time step). We establish the rapid convergence of fifteen minimal Elementary Cellular Automata, showing that their average convergence time to a fixed point scales logarithmically with the size of the automaton. Techniques involve the use of Markov chain analysis and the construction of adequate potential functions. The problem is however left open for twelve other minimal rules, which shows the need to develop this analysis further.
Type de document :
Communication dans un congrès
ACRI 2014, Sep 2014, Krakow, Poland. Springer, Lecture Notes of Computer Science, 8751, Cellular Automata. 〈10.1007/978-3-319-11520-7_62〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01088166
Contributeur : Nazim Fatès <>
Soumis le : jeudi 27 novembre 2014 - 15:01:18
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23

Identifiants

Citation

Nazim Fatès. Quick convergence to a fixed point: A note on asynchronous Elementary Cellular Automata. ACRI 2014, Sep 2014, Krakow, Poland. Springer, Lecture Notes of Computer Science, 8751, Cellular Automata. 〈10.1007/978-3-319-11520-7_62〉. 〈hal-01088166〉

Partager

Métriques

Consultations de la notice

238