Stochastic Cellular Automata Solutions to the Density Classification ProblemWhen Randomness Helps Computing

被引：0
|
作者：
Nazim Fatès
机构：
[1] Nancy Université,INRIA Nancy—Grand Est, LORIA
来源：
Theory of Computing Systems | 2013年 / 53卷
关键词：
Stochastic and probabilistic cellular automata; Density classification problem; Models of spatially distributed computing; Stochastic process;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In the density classification problem, a binary cellular automaton (CA) should decide whether an initial configuration contains more 0s or more 1s. The answer is given when all cells of the CA agree on a given state. This problem is known for having no exact solution in the case of binary deterministic one-dimensional CA.
引用
收藏
页码：223 / 242
页数：19
相关论文
共 42 条
  • [11] The Density Classification Problem in the Context of Continuous Cellular Automata
    Wolnik, Barbara
    Dembowski, Marcin
    Bolt, Witold
    Baetens, Jan M.
    De Baets, Bernard
    CELLULAR AUTOMATA, ACRI 2016, 2016, 9863 : 79 - 87
  • [12] Basins of attraction and the density classification problem for cellular automata
    Bossomaier, T
    Sibley-Punnett, L
    Cranny, T
    VIRTUAL WORLDS, 2000, 1834 : 245 - 255
  • [13] Evolution of cellular automata with memory: The Density Classification Task
    Stone, Christopher
    Bull, Larry
    BIOSYSTEMS, 2009, 97 (02) : 108 - 116
  • [14] Nondeterministic density classification with diffusive probabilistic cellular automata
    Fuks, H
    PHYSICAL REVIEW E, 2002, 66 (06): : 4 - 066106
  • [15] Efficient Solutions of the Density Classification Task in One-Dimensional Cellular Automata: Where Can They Be Found?
    Laboudi, Zakaria
    COMPLEX SYSTEMS, 2020, 29 (03): : 669 - 688
  • [16] Quantum Cellular Automata for Quantum Error Correction and Density Classification
    Guedes, T. L. M.
    Winter, D.
    Mueller, M.
    PHYSICAL REVIEW LETTERS, 2024, 133 (15)
  • [17] Density Classification with Non-Unitary Quantum Cellular Automata
    Wagner, Elisabeth
    Dell'Anna, Federico
    Nigmatullin, Ramil
    K. Brennen, Gavin
    ENTROPY, 2025, 27 (01)
  • [18] Computational Mechanisms for Solving the Density Classification Task by Cellular Automata
    Laboudi, Zakaria
    Chikhi, Salim
    JOURNAL OF CELLULAR AUTOMATA, 2019, 14 (1-2) : 69 - 93
  • [19] Cellular Automata Based Algorithm for Image Density Classification Task
    Anghelescu, Petre
    Stirbu, Cosmin
    PROCEEDINGS OF THE 2014 6TH INTERNATIONAL CONFERENCE ON ELECTRONICS, COMPUTERS AND ARTIFICIAL INTELLIGENCE (ECAI), 2014,
  • [20] EXPLORATIONS OF TERNARY CELLULAR AUTOMATA AND TERNARY DENSITY CLASSIFICATION PROBLEMS
    Fuks, Henryk
    Procyk, Roman
    ACTA PHYSICA POLONICA B PROCEEDINGS SUPPLEMENT, 2019, 12 (01) : 75 - 89
12345