Stochastic Cellular Automata Solutions to the Density Classification Problem - When randomness helps computing

Nazim Fatès 1, *
* Auteur correspondant
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : In the density classification problem, a binary cellular automaton should decide whether an initial configuration contains more 0s or 1s. The answer is given when all cells of the CA agree on a given state (0 or 1). This problem is known for having no exact solution in the case of binary deterministic one-dimensional CA. We investigate how randomness in CA may help us solve the problem. We analyse the behaviour of stochastic CA rules that perform the density classification task. We show that describing stochastic rules as a ''blend'' of deterministic rules allows us to derive quantitative results on the classification time and the classification time of previously studied rules. We introduce a new rule whose effect is to spread defects and to wash them out. This stochastic rule solves the problem with an arbitrary precision, that is, its quality of classification can be made arbitrarily high, though at the price of a longer time to converge. We experimentally demonstrate that this rule exhibits good scaling properties and that it attains qualities of classification never reached so far.
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 2013, 53 (2), pp.223-242. 〈10.1007/s00224-012-9386-3〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00608485
Contributeur : Nazim Fatès <>
Soumis le : mercredi 15 février 2012 - 12:15:18
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 06:30:13

Fichier

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

Identifiants

Citation

Nazim Fatès. Stochastic Cellular Automata Solutions to the Density Classification Problem - When randomness helps computing. Theory of Computing Systems, Springer Verlag, 2013, 53 (2), pp.223-242. 〈10.1007/s00224-012-9386-3〉. 〈inria-00608485v2〉

Partager

Métriques

Consultations de la notice

351

Téléchargements de fichiers

456