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 条
  • [1] Stochastic Cellular Automata Solutions to the Density Classification Problem
    Fates, Nazim
    THEORY OF COMPUTING SYSTEMS, 2013, 53 (02) : 223 - 242
  • [2] A Stochastic Traffic Cellular Automata with Controlled Randomness
    Angeline, Lorita
    Choong, Mei Yeen
    Chua, Bih Lii
    Chin, Renee Ka Yin
    Teo, Kenneth Tze Kin
    2017 IEEE 2ND INTERNATIONAL CONFERENCE ON AUTOMATIC CONTROL AND INTELLIGENT SYSTEMS (I2CACIS), 2017, : 68 - 73
  • [3] Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision
    Fates, Nazim
    28TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2011), 2011, 9 : 284 - 295
  • [4] New Solutions for the Density Classification Task in One Dimensional Cellular Automata
    Laboudi, Zakaria
    Chikhi, Salim
    MODELLING AND IMPLEMENTATION OF COMPLEX SYSTEMS, 2019, 64 : 93 - 105
  • [5] Affinity Classification Problem by Stochastic Cellular Automata
    Bhattacharjee, Kamalika
    Paul, Subrata
    Das, Sukanta
    COMPLEX SYSTEMS, 2023, 32 (03): : 271 - 288
  • [6] Pattern Classification with Temporally Stochastic Cellular Automata
    Paul, Subrata
    Roy, Souvik
    Das, Sukanta
    CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS, AUTOMATA 2023, 2023, 14152 : 137 - 152
  • [7] Cellular Automata with Memory and the Density Classification Task
    Alonso-Sanz, Ramon
    JOURNAL OF CELLULAR AUTOMATA, 2013, 8 (3-4) : 283 - 297
  • [8] Cellular automata with memory and the density classification task
    Alonso-sanz, R. (ramon.alonso@upm.es), 1600, Old City Publishing (08): : 3 - 4
  • [9] COLLABORATIVE EVOLUTIONARY SEARCH FOR DENSITY CLASSIFICATION IN CELLULAR AUTOMATA
    Gog, Anca
    Chira, Camelia
    KEPT 2011: KNOWLEDGE ENGINEERING PRINCIPLES AND TECHNIQUES, 2011, : 223 - 232
  • [10] Evolution of Hybrid Cellular Automata for Density Classification Problem
    Anghelescu, Petre
    SYMMETRY-BASEL, 2024, 16 (05):
12345