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.
Type de document :
Communication dans un congrès
19th International Workshop, AUTOMATA 2013,, Sep 2013, Gießen, Germany. Springer, 8155, pp.31-45, Lecture Notes in Computer Science. 〈10.1007/978-3-642-40867-0_3〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00981691
Contributeur : Nazim Fatès <>
Soumis le : mardi 22 avril 2014 - 16:17:59
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : lundi 10 avril 2017 - 16:37:56

Fichier

logConverge.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Nazim Fatès. A note on the fast convergence of asynchronous Elementary Cellular Automata. 19th International Workshop, AUTOMATA 2013,, Sep 2013, Gießen, Germany. Springer, 8155, pp.31-45, Lecture Notes in Computer Science. 〈10.1007/978-3-642-40867-0_3〉. 〈hal-00981691〉

Partager

Métriques

Consultations de la notice

800

Téléchargements de fichiers

428