Stochastic Cellular Automata Solutions to the Density Classification Problem - When randomness helps computing - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theory of Computing Systems Année : 2013

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

Résumé

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.
Fichier principal
Vignette du fichier
DensityClassifcation.pdf (483.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00608485 , version 1 (13-07-2011)
inria-00608485 , version 2 (15-02-2012)

Identifiants

Citer

Nazim Fatès. Stochastic Cellular Automata Solutions to the Density Classification Problem - When randomness helps computing. Theory of Computing Systems, 2013, 53 (2), pp.223-242. ⟨10.1007/s00224-012-9386-3⟩. ⟨inria-00608485v2⟩
260 Consultations
616 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More