{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T13:04:24Z","timestamp":1774357464766,"version":"3.50.1"},"reference-count":26,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T00:00:00Z","timestamp":1612742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2018YFD1100300"],"award-info":[{"award-number":["2018YFD1100300"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Classification of asynchronous elementary cellular automata (AECAs) was explored in the first place by Fates et al. (Complex Systems, 2004) who employed the asymptotic density of cells as a key metric to measure their robustness to stochastic transitions. Unfortunately, the asymptotic density seems unable to distinguish the robustnesses of all AECAs. In this paper, we put forward a method that goes one step further via adopting a metric entropy (Martin, Complex Systems, 2000), with the aim of measuring the asymptotic mean entropy of local pattern distribution in the cell space of any AECA. Numerical experiments demonstrate that such an entropy-based measure can actually facilitate a complete classification of the robustnesses of all AECA models, even when all local patterns are restricted to length 1. To gain more insights into the complexity concerning the forward evolution of all AECAs, we consider another entropy defined in the form of Kolmogorov\u2013Sinai entropy and conduct preliminary experiments on classifying their uncertainties measured in terms of the proposed entropy. The results reveal that AECAs with low uncertainty tend to converge remarkably faster than models with high uncertainty.<\/jats:p>","DOI":"10.3390\/e23020209","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T23:43:16Z","timestamp":1612914196000},"page":"209","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Entropy-Based Classification of Elementary Cellular Automata under Asynchronous Updating: An Experimental Study"],"prefix":"10.3390","volume":"23","author":[{"given":"Qin","family":"Lei","sequence":"first","affiliation":[{"name":"College of Computer Science, Chongqing University, Chongqing 400044, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2304-4263","authenticated-orcid":false,"given":"Jia","family":"Lee","sequence":"additional","affiliation":[{"name":"College of Computer Science, Chongqing University, Chongqing 400044, China"},{"name":"Chong Key Laboratory of Software Theory and Technology, Chongqing 400044, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"College of Computer Science, Chongqing University, Chongqing 400044, China"},{"name":"Information Center, State Bureau for Letters and Calls, Beijing 100017, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuji","family":"Kawasaki","sequence":"additional","affiliation":[{"name":"Faculty of Science and Engineering, Iwate University, Morioka, Iwate 020-8550, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,8]]},"reference":[{"key":"ref_1","unstructured":"von Neumann, J. (1966). Theory of Self-Reproducing Automata, University of Illinois Press."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-2789(84)90245-8","article-title":"Universality and complexity in cellular automata","volume":"10","author":"Wolfram","year":"1984","journal-title":"Phys. D"},{"key":"ref_3","first-page":"387","article-title":"A guided tour of asynchronous cellular automata","volume":"9","author":"Fates","year":"2014","journal-title":"J. Cell. Autom."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Martinez, G.J., Seck-Tuoh-Mora, J.C., and Zenil, H. (2013). Wolfram\u2019s Classification and Computation in Cellular Automata Classes III and IV, Springer.","DOI":"10.1007\/978-3-642-35482-3_17"},{"key":"ref_5","first-page":"233","article-title":"A note on elementary cellular automata classification","volume":"8","author":"Martinez","year":"2013","journal-title":"J. Cell. Autom."},{"key":"ref_6","first-page":"309","article-title":"Cross-boundary behavioural reprogrammability reveals evidence of pervasive universality","volume":"13","author":"Riedel","year":"2018","journal-title":"Int. J. Unconv. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0167-2789(84)90249-5","article-title":"Structure in asynchronous cellular automata","volume":"10","author":"Ingerson","year":"1984","journal-title":"Phys. Nonlinear Phenom."},{"key":"ref_8","first-page":"1","article-title":"An experimental study of robustness to asynchronism for elementary cellular automata","volume":"16","author":"Fates","year":"2004","journal-title":"Complex Syst."},{"key":"ref_9","first-page":"135","article-title":"Apparent entropy of cellular automata","volume":"12","author":"Martin","year":"2000","journal-title":"Complex Syst."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/584091.584093","article-title":"A Mathematical Theory of Communication","volume":"5","author":"Shannon","year":"2001","journal-title":"Mob. Comput. Commun. Rev."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1350159","DOI":"10.1142\/S0218127413501599","article-title":"Asymptotic behaviour and ratios of complexity in cellular automata","volume":"23","author":"Zenil","year":"2013","journal-title":"Int. J. Bifurc. Chaos"},{"key":"ref_12","first-page":"1629","article-title":"On computing the entropy of cellular automata","volume":"290","author":"Manzini","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gutjahr, T., and Keller, K. (2020). Ordinal pattern based entropies and the Kolmogorov\u2013Sinai entropy: An update. Entropy, 22.","DOI":"10.3390\/e22010063"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Maldonado, A.D., Morales, M., Aguilera, P.A., and Salmeron, A. (2020). Analyzing uncertainty in complex socio-ecological networks. Entropy, 22.","DOI":"10.3390\/e22010123"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00165-016-0379-x","article-title":"On the diversity of asynchronous communication","volume":"28","author":"Chevrou","year":"2016","journal-title":"Form. Asp. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1273","DOI":"10.1007\/BF02188230","article-title":"The Domany-Kinzel cellular automaton phase diagram","volume":"74","author":"Zebende","year":"1994","journal-title":"J. Stat. Phys."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0303-2647(99)00025-8","article-title":"Synchronous and asynchronous updating in cellular automata","volume":"51","year":"1999","journal-title":"BioSystems"},{"key":"ref_18","first-page":"281","article-title":"The structure of the elementary cellular automata rule space","volume":"4","author":"Li","year":"1990","journal-title":"Complex Syst."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Fates, N. (2007). Directed percolation in asynchronous elementary cellular automata: A detailed study. Cellular Automata, Springer.","DOI":"10.1007\/11861201_77"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s10955-006-9254-0","article-title":"Thermodynamic formalism for systems with Markov dynamics","volume":"127","author":"Lecomte","year":"2007","journal-title":"J. Stat. Phys."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s11047-020-09782-7","article-title":"A tutorial on elementary cellular automata with fully asynchronous updating","volume":"19","author":"Fates","year":"2020","journal-title":"Nat. Comput."},{"key":"ref_22","first-page":"2009","article-title":"Asynchronism induces second order phase transitions in elementary cellular automata","volume":"4","author":"Fates","year":"2008","journal-title":"J. Cell. Autom."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.physa.2018.09.195","article-title":"A study on delay-sensitive cellular automata","volume":"515","author":"Roy","year":"2019","journal-title":"Phys. Stat. Mech. Its Appl."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1007\/s11047-012-9340-y","article-title":"Probing robustness of cellular automata through variations of asynchronous updating","volume":"11","author":"Boure","year":"2012","journal-title":"Nat. Comput."},{"key":"ref_25","first-page":"359","article-title":"ECA 184 can implement any logic circuits","volume":"13","author":"Hazari","year":"2018","journal-title":"J. Cell. Autom."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kramer, K., Koehler, M., Fiore, C., and Luz, M. (2017). Emergence of distinct spatial patterns in cellular automata with inertia: A phase transition-like behavior. Entropy, 19.","DOI":"10.3390\/e19030102"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/2\/209\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:21:31Z","timestamp":1760160091000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/2\/209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,8]]},"references-count":26,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["e23020209"],"URL":"https:\/\/doi.org\/10.3390\/e23020209","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,8]]}}}