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

Nazim Fatès 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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 binary, 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 analyse the behaviour of stochastic CA rules, seen as a "blend'' of deterministic CA rules. Using analytical calculations and numerical simulations, we analyse two previously studied rules and present a new rule. We estimate their quality of classification and their average time of classification. We show that the new rule solves the problem with an arbitrary precision. From a practical point of view, this rule is effective and exhibits a high quality of classification, even when the simulation time is kept small.
Type de document :
Communication dans un congrès
Thomas Schwentick and Christoph Drr. Symposium on Theoretical Aspects of Computer Science - STACS2011, Mar 2011, Dortmund, Germany. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 9, pp.284--295, 2011, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.STACS.2011.284〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00521415
Contributeur : Nazim Fatès <>
Soumis le : vendredi 7 janvier 2011 - 14:46:00
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 17:51:32

Fichier

Fates-densityClassif-HALv3-201...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Nazim Fatès. Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision. Thomas Schwentick and Christoph Drr. Symposium on Theoretical Aspects of Computer Science - STACS2011, Mar 2011, Dortmund, Germany. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 9, pp.284--295, 2011, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.STACS.2011.284〉. 〈inria-00521415v3〉

Partager

Métriques

Consultations de la notice

527

Téléchargements de fichiers

514