Restricted Density Classification in One Dimension

Abstract : The density classification task is to determine which of the symbols appearing in an array has the majority. A cellular automaton solving this task is required to converge to a uniform configuration with the majority symbol at each site. It is not known whether a one-dimensional cellular automaton with binary alphabet can classify all Bernoulli random configurations almost surely according to their densities. We show that any cellular automaton that washes out finite islands in linear time classifies all Bernoulli random configurations with parameters close to 0 or 1 almost surely correctly. The proof is a direct application of a “percolation” argument which goes back to Gács (1986).
Type de document :
Communication dans un congrès
Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Lecture Notes in Computer Science, LNCS-9099, pp.238-250, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_18〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01442476
Contributeur : Hal Ifip <>
Soumis le : vendredi 20 janvier 2017 - 16:09:26
Dernière modification le : lundi 23 janvier 2017 - 14:02:49
Document(s) archivé(s) le : vendredi 21 avril 2017 - 15:44:34

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Siamak Taati. Restricted Density Classification in One Dimension. Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Lecture Notes in Computer Science, LNCS-9099, pp.238-250, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_18〉. 〈hal-01442476〉

Partager

Métriques

Consultations de la notice

139

Téléchargements de fichiers

6