{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T12:31:57Z","timestamp":1771849917949,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T00:00:00Z","timestamp":1330992000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1007\/s00224-012-9386-3","type":"journal-article","created":{"date-parts":[[2012,3,5]],"date-time":"2012-03-05T21:12:45Z","timestamp":1330981965000},"page":"223-242","source":"Crossref","is-referenced-by-count":43,"title":["Stochastic Cellular Automata Solutions to the Density Classification Problem"],"prefix":"10.1007","volume":"53","author":[{"given":"Nazim","family":"Fat\u00e8s","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,3,6]]},"reference":[{"issue":"48","key":"9386_CR1","doi-asserted-by":"crossref","first-page":"485,101","DOI":"10.1088\/1751-8113\/42\/48\/485101","volume":"42","author":"R. Alonso-Sanz","year":"2009","unstructured":"Alonso-Sanz, R., Bull, L.: A very effective density classifier two-dimensional cellular automaton with memory. J. Phys. A 42(48), 485,101 (2009)","journal-title":"J. Phys. A"},{"key":"9386_CR2","unstructured":"B\u00e9n\u00e9zit, F.: Distributed average consensus for wireless sensor networks. Ph.D. thesis, EPFL, Lausanne (2009). doi: 10.5075\/epfl-thesis-4509"},{"issue":"1\u20133","key":"9386_CR3","first-page":"1","volume":"52","author":"N. Boccara","year":"2002","unstructured":"Boccara, N., Fuk\u015b, H.: Number-conserving cellular automaton rules. Fundam. Inform. 52(1\u20133), 1\u201313 (2002)","journal-title":"Fundam. Inform."},{"key":"9386_CR4","unstructured":"Busic, A., Fat\u00e8s, N., Mairesse, J., Marcovici, I.: Density classification on infinite lattices and trees (2011). ArXiv: 1111.4582 . Short version to appear in the proceedings of LATIN 2012, LNCS series, vol.\u00a07256"},{"issue":"24","key":"9386_CR5","doi-asserted-by":"crossref","first-page":"4969","DOI":"10.1103\/PhysRevLett.77.4969","volume":"77","author":"M.S. Capcarrere","year":"1996","unstructured":"Capcarrere, M.S., Sipper, M., Tomassini, M.: Two-state, r=1 cellular automaton that classifies density. Phys. Rev. Lett. 77(24), 4969\u20134971 (1996)","journal-title":"Phys. Rev. Lett."},{"key":"9386_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1007\/11861201_59","volume-title":"Cellular Automata","author":"C. Darabos","year":"2006","unstructured":"Darabos, C., Giacobini, M., Tomassini, M.: Scale-free automata networks are not robust in a collective computational task. In: El Yacoubi, S., Chopard, B., Bandini, S. (eds.) Cellular Automata. Lecture Notes in Computer Science, vol. 4173, pp. 512\u2013521. Springer, Berlin (2006)"},{"key":"9386_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2006.05.036","volume":"362","author":"N. Fat\u00e8s","year":"2006","unstructured":"Fat\u00e8s, N., Morvan, M., Schabanel, N., Thierry, E.: Fully asynchronous behavior of double-quiescent elementary cellular automata. Theor. Comput. Sci. 362, 1\u201316 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9386_CR8","first-page":"92","volume":"14","author":"P. G\u00e1cs","year":"1987","unstructured":"G\u00e1cs, P., Kurdiumov, G.L., Levin, L.A.: One-dimensional homogeneous media dissolving finite islands. Probl. Pereda. Inf. 14, 92\u201396 (1987)","journal-title":"Probl. Pereda. Inf."},{"issue":"25","key":"9386_CR9","doi-asserted-by":"crossref","first-page":"5148","DOI":"10.1103\/PhysRevLett.74.5148","volume":"74","author":"M. Land","year":"1995","unstructured":"Land, M., Belew, R.K.: No perfect two-state cellular automata for density classification exists. Phys. Rev. Lett. 74(25), 5148\u20135150 (1995)","journal-title":"Phys. Rev. Lett."},{"key":"9386_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/11553090_47","volume-title":"Advances in Artificial Life","author":"C.L. Martins","year":"2005","unstructured":"Martins, C.L., de Oliveira, P.P.: Evolving sequential combinations of elementary cellular automata rules. In: Capcarrere, M.S., Freitas, A.A., Bentley, P.J., Johnson, C.G., Timmis, J. (eds.) Advances in Artificial Life. Lecture Notes in Computer Science, vol. 3630, pp. 461\u2013470. Springer, Berlin (2005)"},{"key":"9386_CR11","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0167-2789(94)90293-3","volume":"75","author":"M. Mitchell","year":"1994","unstructured":"Mitchell, M., Crutchfield, J.P., Hraber, P.T.: Evolving cellular automata to perform computations: Mechanisms and impediments. Physica D 75, 361\u2013391 (1994)","journal-title":"Physica D"},{"key":"9386_CR12","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.entcs.2009.09.018","volume":"252","author":"G.M.B. Oliveira","year":"2009","unstructured":"Oliveira, G.M.B., Martins, L.G.A., de Carvalho, L.B., Fynn, E.: Some investigations about synchronization and density classification tasks in one-dimensional and two-dimensional cellular automata rule spaces. Electron. Notes Theor. Comput. Sci. 252, 121\u2013142 (2009)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"1\u20133","key":"9386_CR13","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.neucom.2006.07.003","volume":"70","author":"P.P. Oliveira de","year":"2006","unstructured":"de Oliveira, P.P., Bortot, J.C., Oliveira, G.M.: The best currently known class of dynamically equivalent cellular automata rules for density classification. Neurocomputing 70(1\u20133), 35\u201343 (2006)","journal-title":"Neurocomputing"},{"key":"9386_CR14","first-page":"293","volume-title":"Dynamic Patterns in Complex Systems","author":"N.H. Packard","year":"1988","unstructured":"Packard, N.H.: Adaptation toward the edge of chaos. In: Dynamic Patterns in Complex Systems, pp.\u00a0293\u2013301. World Scientific, Singapore (1988)"},{"key":"9386_CR15","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/BF01049718","volume":"67","author":"P.G. S\u00e1 de","year":"1992","unstructured":"de S\u00e1, P.G., Maes, C.: The Gacs-Kurdyumov-Levin automaton revisited. J. Stat. Phys. 67, 507\u2013522 (1992)","journal-title":"J. Stat. Phys."},{"key":"9386_CR16","first-page":"525","volume-title":"ICANN\u201909: Proceedings of the 19th International Conference on Artificial Neural Networks","author":"M. Sch\u00fcle","year":"2009","unstructured":"Sch\u00fcle, M., Ott, T., Stoop, R.: Computing with probabilistic cellular automata. In: ICANN\u201909: Proceedings of the 19th International Conference on Artificial Neural Networks, pp. 525\u2013533. Springer, Berlin (2009)"},{"issue":"3","key":"9386_CR17","doi-asserted-by":"crossref","first-page":"R2081","DOI":"10.1103\/PhysRevE.55.R2081","volume":"55","author":"H. Fuk\u015b","year":"1997","unstructured":"Fuk\u015b, H.: Solution of the density classification problem with two cellular automata rules. Phys. Rev. E 55(3), R2081\u2013R2084 (1997)","journal-title":"Phys. Rev. E"},{"issue":"6","key":"9386_CR18","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.66.066106","volume":"66","author":"H. Fuk\u015b","year":"2002","unstructured":"Fuk\u015b, H.: Nondeterministic density classification with diffusive probabilistic cellular automata. Phys. Rev. E 66(6), 066106 (2002)","journal-title":"Phys. Rev. E"},{"issue":"2","key":"9386_CR19","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.biosystems.2009.05.001","volume":"97","author":"C. Stone","year":"2009","unstructured":"Stone, C., Bull, L.: Evolution of cellular automata with memory: The density classification task. Biosystems 97(2), 108\u2013116 (2009)","journal-title":"Biosystems"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9386-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9386-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9386-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:23Z","timestamp":1558698863000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9386-3"}},"subtitle":["When Randomness Helps Computing"],"short-title":[],"issued":{"date-parts":[[2012,3,6]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["9386"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9386-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,6]]}}}