{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T19:01:56Z","timestamp":1778871716192,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,9,23]],"date-time":"2015-09-23T00:00:00Z","timestamp":1442966400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"crossref","award":["R-252-000-522-112 and R-252-000-470-112"],"award-info":[{"award-number":["R-252-000-522-112 and R-252-000-470-112"]}],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2015,12,28]]},"abstract":"<jats:p>Emergence becomes a distinguishing system feature as system complexity grows with the number of components, interactions, and connectivities. Examples of emergent behaviors include the flocking of birds, traffic jams, and hubs in social networks, among others. Despite significant research interest in recent years, there is a lack of formal methods to understand, identify, and predict emergent behavior in multiagent systems. Existing approaches either require detailed prior knowledge about emergent behavior or are computationally infeasible. This article introduces a grammar-based approach to formalize and identify the existence and extent of emergence without the need for prior knowledge of emergent properties. Our approach is based on weak (basic) emergence that is both generated and autonomous from the underlying agents. We employ formal grammars to capture agent interactions in the forms of words written on a common tape. Our formalism captures agents of diverse types and open systems. We propose an automated approach for the identification of emergent behavior and show its benefits through theoretical and experimental analysis. We also propose a significant reduction of state-space explosion through the use of our proposed degree of interaction metrics. Our experiments using the boids model show the feasibility of our approach but also highlight future avenues of improvement.<\/jats:p>","DOI":"10.1145\/2815502","type":"journal-article","created":{"date-parts":[[2015,9,29]],"date-time":"2015-09-29T19:22:29Z","timestamp":1443554549000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Formalization of Weak Emergence in Multiagent Systems"],"prefix":"10.1145","volume":"26","author":[{"given":"Claudia","family":"Szabo","sequence":"first","affiliation":[{"name":"School of Computer Science, The University of Adelaide, Adelaide, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong Meng","family":"Teo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,9,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/cplx.v12:1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.287.5461.2115a"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"e_1_2_1_4_1","first-page":"67","article-title":"On emergence and explanation","volume":"2","author":"Baas N. A.","year":"1997","unstructured":"N. A. Baas and C. Emmeche . 1997 . On emergence and explanation . Intellectica 2 , 67 -- 83 . N. A. Baas and C. Emmeche. 1997. On emergence and explanation. Intellectica 2, 67--83.","journal-title":"Intellectica"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/cplx.20029"},{"key":"e_1_2_1_6_1","volume-title":"Philosophical perspectives: Mind, causation and world. Philosophical Perspectives Annual","author":"Bedau M. A.","unstructured":"M. A. Bedau . 1997. Philosophical perspectives: Mind, causation and world. Philosophical Perspectives Annual Volume 11 . M. A. Bedau. 1997. Philosophical perspectives: Mind, causation and world. Philosophical Perspectives Annual Volume 11."},{"key":"e_1_2_1_7_1","unstructured":"M. A. Bedau. 2003. Downward causation and the autonomy of weak emergence. Principia 3 3 5--50.  M. A. Bedau. 2003. Downward causation and the autonomy of weak emergence. Principia 3 3 5--50."},{"key":"e_1_2_1_8_1","volume-title":"Adelfe: A methodology for adaptive multi-agent systems engineering. In Engineering Societies in the","author":"Bernon C.","year":"2003","unstructured":"C. Bernon , M.-P. Gleizes , S. Peyruqueou , and G. Picard . 2003 . Adelfe: A methodology for adaptive multi-agent systems engineering. In Engineering Societies in the Agents World III. Springer , 156--169. C. Bernon, M.-P. Gleizes, S. Peyruqueou, and G. Picard. 2003. Adelfe: A methodology for adaptive multi-agent systems engineering. In Engineering Societies in the Agents World III. Springer, 156--169."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems. 1455--1456","author":"Birdsey L.","unstructured":"L. Birdsey and C. Szabo . 2014. An architecture for identifying emergent behavior in multi-agent systems . In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems. 1455--1456 . L. Birdsey and C. Szabo. 2014. An architecture for identifying emergent behavior in multi-agent systems. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems. 1455--1456."},{"key":"e_1_2_1_10_1","first-page":"2","article-title":"Detection and emergence","volume":"25","author":"Bonabeau E.","year":"1997","unstructured":"E. Bonabeau and J. Dessalles . 1997 . Detection and emergence . Intellectica 25 , 2 . E. Bonabeau and J. Dessalles. 1997. Detection and emergence. Intellectica 25, 2.","journal-title":"Intellectica"},{"key":"e_1_2_1_11_1","volume-title":"The Re-emergence of Emergence","author":"Chalmers D. J.","unstructured":"D. J. Chalmers . 2006. Strong and weak emergence . In The Re-emergence of Emergence . Oxford University Press . D. J. Chalmers. 2006. Strong and weak emergence. In The Re-emergence of Emergence. Oxford University Press."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of Winter Simulation Conference, S. Jain, R. R. Creasey, J. Himmelspach, K. P. White, and M. Fu (Eds.). Institute of Electrical and Electronics Engineers, 357--336","author":"Chan W. K. V.","year":"2010","unstructured":"W. K. V. Chan . 2010 . Interaction metric of emergent behaviors in agent-based simulation . In Proceedings of Winter Simulation Conference, S. Jain, R. R. Creasey, J. Himmelspach, K. P. White, and M. Fu (Eds.). Institute of Electrical and Electronics Engineers, 357--336 . W. K. V. Chan. 2010. Interaction metric of emergent behaviors in agent-based simulation. In Proceedings of Winter Simulation Conference, S. Jain, R. R. Creasey, J. Himmelspach, K. P. White, and M. Fu (Eds.). Institute of Electrical and Electronics Engineers, 357--336."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88075-2_5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"C. C. Chen S. B. Nagl and C. D. Clack. 2009b. A formalism for multi-level emergent behaviours in designed component-based systems and agent-based simulations. In From System Complexity to Emergent Properties. Springer-Verlag 101--114.  C. C. Chen S. B. Nagl and C. D. Clack. 2009b. A formalism for multi-level emergent behaviours in designed component-based systems and agent-based simulations. In From System Complexity to Emergent Properties. Springer-Verlag 101--114.","DOI":"10.1007\/978-3-642-02199-2_4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/10919390903041931"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056813"},{"key":"e_1_2_1_17_1","first-page":"515","article-title":"Is anything ever new? Considering emergence","volume":"19","author":"Crutchfield J. P.","year":"1999","unstructured":"J. P. Crutchfield . 1999 . Is anything ever new? Considering emergence . In Complexity , Vol. 19 , 515 -- 537 . Addison-Wesley. J. P. Crutchfield. 1999. Is anything ever new? Considering emergence. In Complexity, Vol. 19, 515--537. Addison-Wesley.","journal-title":"Complexity"},{"key":"e_1_2_1_18_1","first-page":"411","article-title":"Emergent phenomena and complexity","author":"Darley V.","year":"1994","unstructured":"V. Darley . 1994 . Emergent phenomena and complexity . Artificial Life IV , 4, 411 -- 416 . V. Darley. 1994. Emergent phenomena and complexity. Artificial Life IV, 4, 411--416.","journal-title":"Artificial Life"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1159\/000094185"},{"key":"e_1_2_1_20_1","volume-title":"Darwin Among the Machines: The Evolution of Global Intelligence","author":"Dyson G. B.","unstructured":"G. B. Dyson . 1998. Darwin Among the Machines: The Evolution of Global Intelligence . Perseus Books Group . G. B. Dyson. 1998. Darwin Among the Machines: The Evolution of Global Intelligence. Perseus Books Group."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SASO.2010.31"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.298431"},{"key":"e_1_2_1_23_1","unstructured":"J. Fromm. 2007. Types and Forms of Emergence. http:\/\/arxiv.org\/abs\/nlin.AO\/0506028.  J. Fromm. 2007. Types and Forms of Emergence. http:\/\/arxiv.org\/abs\/nlin.AO\/0506028."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of International Conference on Neural Networks and Brain. 1858--1863","author":"Gabbai J. M. E.","unstructured":"J. M. E. Gabbai , H. Yin , W. A. Wright , and N. M. Allinson . 2005. Self-organization, emergence and multi-agent systems . In Proceedings of International Conference on Neural Networks and Brain. 1858--1863 . J. M. E. Gabbai, H. Yin, W. A. Wright, and N. M. Allinson. 2005. Self-organization, emergence and multi-agent systems. In Proceedings of International Conference on Neural Networks and Brain. 1858--1863."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Winter Simulation Conference. 712--721","author":"Gore R.","unstructured":"R. Gore and P. F. Reynolds . 2008. Applying causal inference to understand emergent behavior . In Proceedings of the Winter Simulation Conference. 712--721 . R. Gore and P. F. Reynolds. 2008. Applying causal inference to understand emergent behavior. In Proceedings of the Winter Simulation Conference. 712--721."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom.2010.107"},{"key":"e_1_2_1_27_1","article-title":"A survey of agent-based modeling practices (January 1998 to July 2008)","volume":"12","author":"Heath B.","year":"2009","unstructured":"B. Heath , R. Hill , and F. Ciarallo . 2009 . A survey of agent-based modeling practices (January 1998 to July 2008) . Journal of Artificial Societies and Social Simulation 12 , 4, 9+. B. Heath, R. Hill, and F. Ciarallo. 2009. A survey of agent-based modeling practices (January 1998 to July 2008). Journal of Artificial Societies and Social Simulation 12, 4, 9+.","journal-title":"Journal of Artificial Societies and Social Simulation"},{"key":"e_1_2_1_28_1","volume-title":"Emergence: From Chaos To Order","author":"Holland J. H.","year":"1997","unstructured":"J. H. Holland . 1997 . Emergence: From Chaos To Order . Addison Wesley . J. H. Holland. 1997. Emergence: From Chaos To Order. Addison Wesley."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92157-8_14"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"J. Hopcroft R. Motwani and J. Ullman. 2001. Introduction to Automata Theory Languages and Computation. Addison-Wesley.   J. Hopcroft R. Motwani and J. Ullman. 2001. Introduction to Automata Theory Languages and Computation. Addison-Wesley.","DOI":"10.1145\/568438.568455"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11023-008-9123-5"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems-Volume 1. 481--488","author":"Jacyno M.","unstructured":"M. Jacyno , S. Bullock , M. Luck , and T. R. Payne . 2009. Emergent service provisioning and demand estimation through self-organizing agent communities . In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems-Volume 1. 481--488 . M. Jacyno, S. Bullock, M. Luck, and T. R. Payne. 2009. Emergent service provisioning and demand estimation through self-organizing agent communities. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems-Volume 1. 481--488."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ress.2006.01.008"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1162\/106454603321489518"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of IEEE International Conference on Industrial Economics. 1295--1300","author":"Li Z.","year":"2006","unstructured":"Z. Li , C. H. Sim , and M. Y. H. Low . 2006 . A survey of emergent behaviour and impacts in agent-based systems . In Proceedings of IEEE International Conference on Industrial Economics. 1295--1300 . Z. Li, C. H. Sim, and M. Y. H. Low. 2006. A survey of emergent behaviour and impacts in agent-based systems. In Proceedings of IEEE International Conference on Industrial Economics. 1295--1300."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of 14th World Multi-Conference on Systemics, Cybernetics and Informatics. 25--34","author":"Manley E. J.","unstructured":"E. J. Manley and T. Cheng . 2010. Understanding road congestion as an emergent property of traffic networks . In Proceedings of 14th World Multi-Conference on Systemics, Cybernetics and Informatics. 25--34 . E. J. Manley and T. Cheng. 2010. Understanding road congestion as an emergent property of traffic networks. In Proceedings of 14th World Multi-Conference on Systemics, Cybernetics and Informatics. 25--34."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 2. 773--780","author":"Melo F. S.","unstructured":"F. S. Melo and M. Veloso . 2009. Learning of coordination: Exploiting sparse interactions in multiagent systems . In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 2. 773--780 . F. S. Melo and M. Veloso. 2009. Learning of coordination: Exploiting sparse interactions in multiagent systems. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 2. 773--780."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cogsys.2012.06.003"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of IEEE Mountain Workshop on Adaptive and Learning Systems. 78--84","author":"Mnif M.","unstructured":"M. Mnif and C. Muller-Schloer . 2006. Quantitative emergence . In Proceedings of IEEE Mountain Workshop on Adaptive and Learning Systems. 78--84 . M. Mnif and C. Muller-Schloer. 2006. Quantitative emergence. In Proceedings of IEEE Mountain Workshop on Adaptive and Learning Systems. 78--84."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217935.1217964"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4024\/07MO10A.jbpc.10.01"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190326.1190330"},{"key":"e_1_2_1_43_1","first-page":"91","article-title":"Emergent properties","volume":"31","author":"O\u2019Conner T.","year":"1994","unstructured":"T. O\u2019Conner . 1994 . Emergent properties . American Philosophical Quarterly 31 , 2, 91 -- 104 . T. O\u2019Conner. 1994. Emergent properties. American Philosophical Quarterly 31, 2, 91--104.","journal-title":"American Philosophical Quarterly"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of 19th Conference on Local Computer Networks. 228--240","author":"Ramakrishnan K. K.","unstructured":"K. K. Ramakrishnan and H. Yang . 1994. The Ethernet capture effect: Analysis and solution . In Proceedings of 19th Conference on Local Computer Networks. 228--240 . K. K. Ramakrishnan and H. Yang. 1994. The Ethernet capture effect: Analysis and solution. In Proceedings of 19th Conference on Local Computer Networks. 228--240."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of 2nd International Workshop on Engineering Emergence in Decentralized Autonomic Systems. 1--10","author":"Randles M.","unstructured":"M. Randles , H. Zhu , and A. Taleb-Bendiab . 2007. A formal approach to the engineering of emergence and its recurrence . In Proceedings of 2nd International Workshop on Engineering Emergence in Decentralized Autonomic Systems. 1--10 . M. Randles, H. Zhu, and A. Taleb-Bendiab. 2007. A formal approach to the engineering of emergence and its recurrence. In Proceedings of 2nd International Workshop on Engineering Emergence in Decentralized Autonomic Systems. 1--10."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37406"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1030033.1030079"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. 669--676","author":"Salazar Salazar N.","unstructured":"N. Salazar Salazar , J. Rodriguez-Aguilar , J. Arcos , A. Peleteiro , and J. Burguillo-Rial . 2011. Emerging cooperation on complex networks . In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. 669--676 . N. Salazar Salazar, J. Rodriguez-Aguilar, J. Arcos, A. Peleteiro, and J. Burguillo-Rial. 2011. Emerging cooperation on complex networks. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. 669--676."},{"key":"e_1_2_1_49_1","unstructured":"A. K. Seth. 2008. Measuring emergence via nonlinear Granger causality. Artificial Life XI 324 1 545--552.  A. K. Seth. 2008. Measuring emergence via nonlinear Granger causality. Artificial Life XI 324 1 545--552."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the Winter Simulation Conference. 2412--2423","author":"Szabo C.","unstructured":"C. Szabo and Y. M. Teo . 2012a. An integrated approach for the validation of emergence in component-based simulation models . In Proceedings of the Winter Simulation Conference. 2412--2423 . C. Szabo and Y. M. Teo. 2012a. An integrated approach for the validation of emergence in component-based simulation models. In Proceedings of the Winter Simulation Conference. 2412--2423."},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"C. Szabo and Y. M. Teo. 2012b. Semantic validation of emergent properties in component-based simulation models. Ontology Epistemology and Teleology of Modeling and Simulation Philosophical Foundations for Intelligent M&S Applications. 319--333.  C. Szabo and Y. M. Teo. 2012b. Semantic validation of emergent properties in component-based simulation models. Ontology Epistemology and Teleology of Modeling and Simulation Philosophical Foundations for Intelligent M&S Applications. 319--333.","DOI":"10.1007\/978-3-642-31140-6_16"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486092.2486122"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICAC.2005.20"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00138-008-0132-4"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2815502","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2815502","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:14Z","timestamp":1750225394000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2815502"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,23]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12,28]]}},"alternative-id":["10.1145\/2815502"],"URL":"https:\/\/doi.org\/10.1145\/2815502","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,23]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}