| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
A note on the fast convergence of asynchronous Elementary Cellular Automata
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.
Cited literature [8 references]
https://hal.inria.fr/hal-00981691
Contributor : Nazim Fatès <>
Submitted on : Tuesday, April 22, 2014 - 4:17:59 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on: : Monday, April 10, 2017 - 4:37:56 PM
Contributor : Nazim Fatès <>
Submitted on : Tuesday, April 22, 2014 - 4:17:59 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on: : Monday, April 10, 2017 - 4:37:56 PM
File
logConverge.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution 4.0 International License