Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2010

Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision

Nazim A. Fatès

Résumé

The density classification problem consists in using a binary cellular automaton (CA) to decide whether an initial configuration contains more 0s or 1s. This problem is known for having no exact solution in the case of deterministic one-dimensional CA. Stochastic cellular automata have been studied as an alternative for solving the problem. This paper is aimed at presenting techniques to describe stochastic CA rules as a ``blend'' of deterministic CA rules. We analyse two previously studied rules and present a new rule that solves the problem with an arbitrary precision. Using analytical calculations and numerical simulations, we estimate how the quality of classification and the average time of classification varies as a function of the blending parameter. From a practical point of view, simulations show that for a great range of values, the new rule exhibits a quality of classification never attained so far.
Fichier principal
Vignette du fichier
densityClassif.pdf (423.38 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00521415 , version 1 (27-09-2010)
inria-00521415 , version 2 (27-10-2010)
inria-00521415 , version 3 (07-01-2011)

Identifiants

  • HAL Id : inria-00521415 , version 2

Citer

Nazim A. Fatès. Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision. 2010. ⟨inria-00521415v2⟩
250 Consultations
720 Téléchargements

Partager

Gmail Facebook X LinkedIn More