{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T04:29:52Z","timestamp":1779337792715,"version":"3.51.4"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T00:00:00Z","timestamp":1456099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2016,5,2]]},"abstract":"<jats:p>Discrete event models are widely used to replicate, analyze, and understand complex systems. DEVS (Discrete Event System Specification) formalism enables hierarchical modeling, so it provides an efficiency in the model development of complex models. However, the hierarchical modeling incurs prolonged simulation executions due to indirect event exchanges through the model hierarchy. Although direct event paths are applied to mitigate this overhead, the situation becomes even worse when a model changes its structures during simulation execution, called a dynamic structure model. This article suggests Coupling Relation Graph (CRG) and Strongly Coupled Component (SCC) concepts to improve hierarchical and dynamic structure DEVS simulation execution. CRG is a directed graph representing DEVS model structure, and SCC is a group of connected components in a CRG. Using CRG and SCC, this article presents (1) how to develop CRG from a DEVS model and (2) how to construct and update direct event paths with respect to dynamic structural changes. In particular, compared to the previous works, the proposed method focuses on the reduction of the updating costs for the direct event paths. Through theoretical and empirical analyses, this article shows that the proposed method significantly reduces the simulation execution time, especially when a simulation model contains lots of components and changes its model structures frequently. We expect that the proposed method would support the faster simulation executions of complex hierarchical and dynamic structure models.<\/jats:p>","DOI":"10.1145\/2875356","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T13:07:16Z","timestamp":1456146436000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Flattening Algorithm for Hierarchical and Dynamic Structure Discrete Event Models"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4681-5059","authenticated-orcid":false,"given":"Jang Won","family":"Bae","sequence":"first","affiliation":[{"name":"Korea Advanced Institute of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sang Won","family":"Bae","sequence":"additional","affiliation":[{"name":"Kyonggi University, Suwon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Il-Chul","family":"Moon","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tag Gon","family":"Kim","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,22]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549713504983"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8667.2010.00650.x"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1057\/jos.2014.37"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1878537.1878670"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2429759.2430295"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549714551291"},{"key":"e_1_2_2_7_1","volume-title":"Dynamics of Complex Systems","author":"Bar-Yam Yaneer","unstructured":"Yaneer Bar-Yam . 1997. Dynamics of Complex Systems . Addison-Wesley , Reading, MA . 213 pages. Yaneer Bar-Yam. 1997. Dynamics of Complex Systems. Addison-Wesley, Reading, MA. 213 pages."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/231104.231107"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549714529833"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549712454931"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1639809.1655380"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the 2010 Summer Computer Simulation Conference. Society for Computer Simulation International, 209--218","author":"Chen Bin","year":"2010","unstructured":"Bin Chen and Hans Vangheluwe . 2010 . Symbolic flattening of DEVS models . In Proceedings of the 2010 Summer Computer Simulation Conference. Society for Computer Simulation International, 209--218 . Bin Chen and Hans Vangheluwe. 2010. Symbolic flattening of DEVS models. In Proceedings of the 2010 Summer Computer Simulation Conference. Society for Computer Simulation International, 209--218."},{"key":"e_1_2_2_13_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2001. Transitive closure of a directed graph . In Introduction to Algorithms . MIT Press and McGraw-Hill , 632--634. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Transitive closure of a directed graph. In Introduction to Algorithms. MIT Press and McGraw-Hill, 632--634."},{"key":"e_1_2_2_14_1","volume-title":"Parallel and Distribution Simulation Systems","author":"Fujimoto Richard M.","unstructured":"Richard M. Fujimoto . 1999. Parallel and Distribution Simulation Systems . John Wiley & Sons , New York, NY . Richard M. Fujimoto. 1999. Parallel and Distribution Simulation Systems. John Wiley & Sons, New York, NY."},{"key":"e_1_2_2_15_1","volume-title":"Mathematical Structures for Computer Science","author":"Gersting Judith L.","unstructured":"Judith L. Gersting . 2007. Mathematical Structures for Computer Science . W. H. Freeman . 807 pages. Judith L. Gersting. 2007. Mathematical Structures for Computer Science. W. H. Freeman. 807 pages."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/DISTRA.2005.18"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the International Workshop on Modeling, Analysis, and Simulation on Computer and Telecommunication Systems (MASCOTS\u201993)","author":"Kumar","unstructured":"Kumar K. Goswami and Ravishankar K. Iyer. 1993. Use of hybrid and hierarchical simulation to reduce computation costs . In Proceedings of the International Workshop on Modeling, Analysis, and Simulation on Computer and Telecommunication Systems (MASCOTS\u201993) . Society for Computer Simulation International, San Diego, CA, 197--202. Kumar K. Goswami and Ravishankar K. Iyer. 1993. Use of hybrid and hierarchical simulation to reduce computation costs. In Proceedings of the International Workshop on Modeling, Analysis, and Simulation on Computer and Telecommunication Systems (MASCOTS\u201993). Society for Computer Simulation International, San Diego, CA, 197--202."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/PADS.2012.31"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-006-0014-y"},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the 2007 Spring Simulation Multiconference","volume":"2","author":"Himmelspach Jan","unstructured":"Jan Himmelspach , Roland Ewald , Stefan Leye , and Adelinde M. Uhrmacher . 2007. Parallel and distributed simulation of parallel DEVS models . In Proceedings of the 2007 Spring Simulation Multiconference , Vol. 2 . Society for Computer Simulation International, 249--256. Jan Himmelspach, Roland Ewald, Stefan Leye, and Adelinde M. Uhrmacher. 2007. Parallel and distributed simulation of parallel DEVS models. In Proceedings of the 2007 Spring Simulation Multiconference, Vol. 2. Society for Computer Simulation International, 249--256."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5964\/jspp.v1i1.36"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the High Performance Computing Symposium (HPC\u201904)","author":"Hu Xiaolin","unstructured":"Xiaolin Hu and Bernard P. Zeigler . 2004. A high performance simulation engine for large-scale cellular DEVS models . In Proceedings of the High Performance Computing Symposium (HPC\u201904) . 3--8. Xiaolin Hu and Bernard P. Zeigler. 2004. A high performance simulation engine for large-scale cellular DEVS models. In Proceedings of the High Performance Computing Symposium (HPC\u201904). 3--8."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549705052227"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of 2005 DEVS Symposium. 2--8.","author":"Hwang Moon Ho","year":"2005","unstructured":"Moon Ho Hwang . 2005 . Tutorial: Verification of real-time system based on schedule-preserved DEVS . In Proceedings of 2005 DEVS Symposium. 2--8. Moon Ho Hwang. 2005. Tutorial: Verification of real-time system based on schedule-preserved DEVS. In Proceedings of 2005 DEVS Symposium. 2--8."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2009.52"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1177\/003754970107600603"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the Simulation Symposium 2000 (SS\u201900)","author":"Kim Kihyung","year":"2000","unstructured":"Kihyung Kim , Wonseok Kang , Bong Sagong , and Hyungon Seo . 2000 . Efficient distributed simulation of hierarchical devs models: Transforming model structure into a non-hierarchical one . In Proceedings of the Simulation Symposium 2000 (SS\u201900) . IEEE Computer Society, Washington, DC, 227--233. Kihyung Kim, Wonseok Kang, Bong Sagong, and Hyungon Seo. 2000. Efficient distributed simulation of hierarchical devs models: Transforming model structure into a non-hierarchical one. In Proceedings of the Simulation Symposium 2000 (SS\u201900). IEEE Computer Society, Washington, DC, 227--233."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2346616.2346630"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the Summer Computer Simulation Conference.","author":"Lee Wan Bok","year":"2003","unstructured":"Wan Bok Lee and Tag Gon Kim . 2003 . Simulation speedup for DEVS models by composition-based compilation . In Proceedings of the Summer Computer Simulation Conference. Wan Bok Lee and Tag Gon Kim. 2003. Simulation speedup for DEVS models by composition-based compilation. In Proceedings of the Summer Computer Simulation Conference."},{"key":"e_1_2_2_30_1","unstructured":"Seong Yong Lim and Tag Gon Kim. 2001. Hybrid modeling and simulation methodology based on DEVS formalism. In Summer Computer Simulation.  Seong Yong Lim and Tag Gon Kim. 2001. Hybrid modeling and simulation methodology based on DEVS formalism. In Summer Computer Simulation."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1878537.1878667"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.3384\/ecp09430032"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the 1st Open International Conference on Modeling & Simulation (OICMS&rsquo;& Simulation (OICMS&rsquo;\u201905)","author":"Muzy Alexander","unstructured":"Alexander Muzy and James J. Nutaro . 2005. Algorithms for efficient implementations of the DEVS & DSDEVS abstract simulators . In Proceedings of the 1st Open International Conference on Modeling & Simulation (OICMS&rsquo;& Simulation (OICMS&rsquo;\u201905) . 1--8. Alexander Muzy and James J. Nutaro. 2005. Algorithms for efficient implementations of the DEVS & DSDEVS abstract simulators. In Proceedings of the 1st Open International Conference on Modeling & Simulation (OICMS&rsquo;& Simulation (OICMS&rsquo;\u201905). 1--8."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793962314500123"},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of the 2003 Summer Computer Simulation Conference. 139--146","author":"Posse Ernesto","year":"2003","unstructured":"Ernesto Posse , Jean-S\u00e9bastien Bolduc , and Hans Vangheluwe . 2003 . Generation of DEVS modelling and simulation environments . In Proceedings of the 2003 Summer Computer Simulation Conference. 139--146 . Ernesto Posse, Jean-S\u00e9bastien Bolduc, and Hans Vangheluwe. 2003. Generation of DEVS modelling and simulation environments. In Proceedings of the 2003 Summer Computer Simulation Conference. 139--146."},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"H. Pranevicius L. Simaitis M. Pranevicius and O. Pranevicius. 2011. Piece-linear aggregates for formai specification and simulation of hybrid systems: Pharmacokinetics patient-controlled analgesia. Elektronika ir Elektrotechnika 110 4 (2011) 81--84.  H. Pranevicius L. Simaitis M. Pranevicius and O. Pranevicius. 2011. Piece-linear aggregates for formai specification and simulation of hybrid systems: Pharmacokinetics patient-controlled analgesia. Elektronika ir Elektrotechnika 110 4 (2011) 81--84.","DOI":"10.5755\/j01.eee.110.4.293"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpat.2008.11.003"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1639809.1655372"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.31.6.1030"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpat.2011.01.006"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2431518.2431875"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1639809.1655391"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/384169.384173"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CACSD.2000.900199"},{"key":"e_1_2_2_45_1","first-page":"73","article-title":"Improved cellular models with parallel cell-DEVS","volume":"17","author":"Wainer Gabriel","year":"2000","unstructured":"Gabriel Wainer . 2000 . Improved cellular models with parallel cell-DEVS . Transactions of the SCS 17 , 2 (2000), 73 -- 89 . Gabriel Wainer. 2000. Improved cellular models with parallel cell-DEVS. Transactions of the SCS 17, 2 (2000), 73--89.","journal-title":"Transactions of the SCS"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1177\/003754970107600102"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1161734.1161748"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1177\/0037549709359357"},{"key":"e_1_2_2_49_1","first-page":"291","article-title":"Variable structure modelling methodology: An adaptive computer architecture example","volume":"7","author":"Zeigler Bernard P.","year":"1990","unstructured":"Bernard P. Zeigler , Tag Gon Kim , and Chilgee Lee . 1990 . Variable structure modelling methodology: An adaptive computer architecture example . Transactions of the Society for Computer Simulation 7 , 4 (1990), 291 -- 320 . Bernard P. Zeigler, Tag Gon Kim, and Chilgee Lee. 1990. Variable structure modelling methodology: An adaptive computer architecture example. Transactions of the Society for Computer Simulation 7, 4 (1990), 291--320.","journal-title":"Transactions of the Society for Computer Simulation"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/318242.318513"},{"key":"e_1_2_2_51_1","volume-title":"Theory of Modeling and Simulation","author":"Zeigler Bernard P.","unstructured":"Bernard P. Zeigler , Herbert Praehofer , and Tag Gon Kim . 2000. Theory of Modeling and Simulation ( 2 nd ed.). Vol. 132 . Academic Press . DOI:http:\/\/dx.doi.org\/10.1159\/000074301 10.1159\/000074301 Bernard P. Zeigler, Herbert Praehofer, and Tag Gon Kim. 2000. Theory of Modeling and Simulation (2nd ed.). Vol. 132. Academic Press. DOI:http:\/\/dx.doi.org\/10.1159\/000074301","edition":"2"},{"key":"e_1_2_2_52_1","volume-title":"Sarjoughian","author":"Zeigler Bernard P.","year":"2013","unstructured":"Bernard P. Zeigler and Hessam S . Sarjoughian . 2013 . Dynamic structure: Agent modeling and publish\/subscribe. In Guide to Modeling and Simulation of Systems of Systems. Springer , 125--143. Bernard P. Zeigler and Hessam S. Sarjoughian. 2013. Dynamic structure: Agent modeling and publish\/subscribe. In Guide to Modeling and Simulation of Systems of Systems. Springer, 125--143."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90078-4"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2875356","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2875356","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:36Z","timestamp":1750227156000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2875356"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,22]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,5,2]]}},"alternative-id":["10.1145\/2875356"],"URL":"https:\/\/doi.org\/10.1145\/2875356","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"value":"1049-3301","type":"print"},{"value":"1558-1195","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,22]]},"assertion":[{"value":"2014-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}