Skip to Main content Skip to Navigation
Conference papers

A note on the fast convergence of 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 : We tackle the problem of the classification of elementary cellular automata when the cells are updated in with a fully asynchronous scheme (one cell is selected at random at each time step). We establish a proof of convergence in logarithmic time as a function of the size of the automaton. Techniques involve a direct Markov chain analysis or the construction of potential function whose convergence rate is bounded by a particular martingale.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Nazim Fatès Connect in order to contact the contributor
Submitted on : Tuesday, April 22, 2014 - 4:17:59 PM
Last modification on : Saturday, June 25, 2022 - 7:41:50 PM
Long-term archiving on: : Monday, April 10, 2017 - 4:37:56 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Nazim Fatès. A note on the fast convergence of asynchronous Elementary Cellular Automata. 19th International Workshop, AUTOMATA 2013,, Sep 2013, Gießen, Germany. pp.31-45, ⟨10.1007/978-3-642-40867-0_3⟩. ⟨hal-00981691⟩



Record views


Files downloads