Stochastic Cellular Automata Solutions to the Density Classification Problem
作者： Nazim Fatès
DOI: 10.1007/S00224-012-9386-3
关键词:
摘要: In the density classification problem, a binary cellular automaton should decide whether an initial configuration contains more 0s or 1s. The answer is given when all cells of CA agree on state (0 1). This problem known for having no exact solution in case deterministic one-dimensional CA. We investigate how randomness may help us solve problem. analyse behaviour stochastic rules that perform task. show describing as ''blend'' allows to derive quantitative results time and previously studied rules. introduce new rule whose effect spread defects wash them out. solves with arbitrary precision, is, its quality can be made arbitrarily high, though at price longer converge. experimentally demonstrate this exhibits good scaling properties it attains qualities never reached so far.
springer.com
archives-ouvertes.fr
sci-hub.se 参考文章(22)
Martin Schüle, Thomas Ott, Ruedi Stoop, Computing with Probabilistic Cellular Automata international conference on artificial neural networks. pp. 525- 533 ,(2009) , 10.1007/978-3-642-04277-5_53
Christian Darabos, Mario Giacobini, Marco Tomassini, Scale-Free Automata Networks Are Not Robust in a Collective Computational Task Lecture Notes in Computer Science. pp. 512- 521 ,(2006) , 10.1007/11861201_59
Henryk Fuks-acute, Solution of the density classification problem with two cellular automata rules Physical Review E. ,vol. 55, pp. R2081- R2084 ,(1997) , 10.1103/PHYSREVE.55.R2081
Michael F. Shlesinger, H. Haken, Arnold J. Mandell, J. A. Scott Kelso, Dynamic patterns in complex systems World Scientific. ,(1988)
Henryk Fukś, Nino Boccara, Number-conserving cellular automaton rules Fundamenta Informaticae. ,vol. 52, pp. 1- 13 ,(2002)
Florence Bénézit, Distributed average consensus for wireless sensor networks EPFL. ,(2009) , 10.5075/EPFL-THESIS-4509
Mark Land, Richard K Belew, None, No perfect two-state cellular automata for density classification exists. Physical Review Letters. ,vol. 74, pp. 5148- 5150 ,(1995) , 10.1103/PHYSREVLETT.74.5148
Pedro P.B. de Oliveira, José C. Bortot, Gina M.B. Oliveira, The best currently known class of dynamically equivalent cellular automata rules for density classification Neurocomputing. ,vol. 70, pp. 35- 43 ,(2006) , 10.1016/J.NEUCOM.2006.07.003
Ramón Alonso-Sanz, Larry Bull, A very effective density classifier two-dimensional cellular automaton with memory Journal of Physics A. ,vol. 42, pp. 485101- ,(2009) , 10.1088/1751-8113/42/48/485101
Gina MB Oliveira, Luiz GA Martins, Laura B. de Carvalho, Enrique Fynn, None, Some Investigations About Synchronization and Density Classification Tasks in One-dimensional and Two-dimensional Cellular Automata Rule Spaces Electronic Notes in Theoretical Computer Science. ,vol. 252, pp. 121- 142 ,(2009) , 10.1016/J.ENTCS.2009.09.018