Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

https://hal.inria.fr/hal-01088166
Contributor : Nazim Fatès <>
Submitted on : Thursday, November 27, 2014 - 3:01:18 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM

Identifiers

Citation

Nazim Fatès. Quick convergence to a fixed point: A note on asynchronous Elementary Cellular Automata. ACRI 2014, Sep 2014, Krakow, Poland. ⟨10.1007/978-3-319-11520-7_62⟩. ⟨hal-01088166⟩

Share

Metrics

Record views

315