{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T09:11:19Z","timestamp":1789636279004,"version":"4.0.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T00:00:00Z","timestamp":1506470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1446900"],"award-info":[{"award-number":["1446900"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>We propose techniques to construct abstractions for nonlinear dynamics in terms of relations expressed in linear arithmetic. Such relations are useful for translating the closed loop verification problem of control software with continuous-time, nonlinear plant models into discrete and linear models that can be handled by efficient software verification approaches for discrete-time systems. We construct relations using Taylor model based flowpipe construction and the systematic composition of relational abstractions for smaller components. We focus on developing efficient schemes for the special case of composing abstractions for linear and nonlinear components. We implement our ideas using a relational abstraction system, using the resulting abstraction inside the verification tool NuXMV, which implements numerous SAT\/SMT solver-based verification techniques for discrete systems. Finally, we evaluate the application of relational abstractions for verifying properties of time triggered controllers, comparing with the Flow* tool. We conclude that relational abstractions are a promising approach towards nonlinear hybrid system verification, capable of proving properties that are beyond the reach of tools such as Flow*. At the same time, we highlight the need for improvements to existing linear arithmetic SAT\/SMT solvers to better support reasoning with large relational abstractions.<\/jats:p>","DOI":"10.1145\/3126522","type":"journal-article","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T12:33:53Z","timestamp":1506515633000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Compositional Relational Abstraction for Nonlinear Hybrid Systems"],"prefix":"10.1145","volume":"16","author":[{"given":"Xin","family":"Chen","sequence":"first","affiliation":[{"name":"University of Colorado Boulder, Boulder, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergio","family":"Mover","sequence":"additional","affiliation":[{"name":"University of Colorado Boulder, Boulder, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sriram","family":"Sankaranarayanan","sequence":"additional","affiliation":[{"name":"University of Colorado Boulder, Boulder, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465787.2465797"},{"key":"e_1_2_1_2_1","volume-title":"Proc. of ARCH\u201915 (EPiC Series in Computer Science)","volume":"34","author":"Althoff M.","year":"2015"},{"key":"e_1_2_1_3_1","volume-title":"Proc. of TACAS\u201903 (LNCS)","volume":"2619","author":"Alur R."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 6th International Workshop on Hybrid Systems: Computation and Control (HSCC\u201903)","volume":"2623","author":"Alur R."},{"key":"e_1_2_1_5_1","volume-title":"Principles of Model Checking","author":"Baier C."},{"key":"e_1_2_1_6_1","volume-title":"Modern Map Methods in Particle Beam Physics. Advances in Imaging and Electron Physics","author":"Berz M."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024467732637"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1946284.1946291"},{"key":"e_1_2_1_9_1","volume-title":"Proc. of RV\u201915 (LNCS)","volume":"9333","author":"Cameron F."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_22"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.70"},{"key":"e_1_2_1_13_1","volume-title":"Proc. of CAV\u201913 (LNCS)","volume":"8044","author":"Chen X."},{"key":"e_1_2_1_14_1","unstructured":"X. Chen S. Dutta and S. Sankaranarayanan. 2017. Formal Verification of a Multi-Basal Insulin Infusion Control Model. (2017). Cf. http:\/\/www.cs.colorado.edu\/\/srirams\/projects\/ap-verification-project-page.html.  X. Chen S. Dutta and S. Sankaranarayanan. 2017. Formal Verification of a Multi-Basal Insulin Infusion Control Model. (2017). Cf. http:\/\/www.cs.colorado.edu\/\/srirams\/projects\/ap-verification-project-page.html."},{"key":"e_1_2_1_15_1","volume-title":"Proc. of the 37th IEEE Real-Time Systems Symposium (RTSS\u201916)","author":"Chen X."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46681-0_4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-016-0257-4"},{"key":"e_1_2_1_18_1","first-page":"1740","article-title":"Meal simulation model of the glucose-insulin system","volume":"1","author":"Man C. Dalla","year":"2006","journal-title":"IEEE Transactions on Biomedical Engineering"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03845-7_9"},{"key":"e_1_2_1_20_1","volume-title":"Proc. of TACAS\u201908 (LNCS)","volume":"4963","author":"de Moura L. M."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14295-6_17"},{"key":"e_1_2_1_22_1","volume-title":"SPIN\u201916 (Lecture Notes in Computer Science)","author":"Dragomir Iulia"},{"key":"e_1_2_1_23_1","unstructured":"B. Dutertre and L. de Moura. 2006. The YICES SMT Solver. (2006). Cf. http:\/\/yices.csl.sri.com\/tool-paper.pdf.  B. Dutertre and L. de Moura. 2006. The YICES SMT Solver. (2006). Cf. http:\/\/yices.csl.sri.com\/tool-paper.pdf."},{"key":"e_1_2_1_24_1","volume-title":"Proc. of SEFM\u201911 (LNCS)","volume":"7041","author":"Eggers A."},{"key":"e_1_2_1_25_1","first-page":"209","article-title":"Efficient Solving of Large Non-linear Arithmetic Constraint Systems with Complex Boolean Structure. JSAT\u2014Journal on Satisfiability, Boolean Modeling and Computation","volume":"1","author":"Fr\u00e4nzle M.","year":"2007","journal-title":"Special Issue on SAT\/CP Integration"},{"key":"e_1_2_1_26_1","volume-title":"Proc. of CAV\u201911 (LNCS)","volume":"6806","author":"Frehse G."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38574-2_14"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 13th International Conference on Formal Methods in Computer-Aided Design (FMCAD\u201913)","author":"Gao S."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2562059.2562126"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46681-0_15"},{"key":"e_1_2_1_32_1","first-page":"379","article-title":"Taylor models and other validated functional inclusion methods","volume":"4","author":"Makino K.","year":"2003","journal-title":"J. Pure and Applied Mathematics"},{"key":"e_1_2_1_33_1","first-page":"2472","article-title":"A System Model of Oral Glucose Absorption: Validation on Gold Standard Data. Biomedical Engineering","volume":"53","author":"Man C. Dalla","year":"2006","journal-title":"IEEE Transactions on"},{"key":"e_1_2_1_34_1","volume-title":"Proc. of HSCC\u201900 (LNCS)","volume":"1790","author":"Mitchell I."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"S. Mover A. Cimatti A. Tiwari and S. Tonetta. 2013. Time-aware relational abstractions for hybrid systems. In EMSOFT\u201913. 1--10.   S. Mover A. Cimatti A. Tiwari and S. Tonetta. 2013. Time-aware relational abstractions for hybrid systems. In EMSOFT\u201913. 1--10.","DOI":"10.1109\/EMSOFT.2013.6658592"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/050638448"},{"key":"e_1_2_1_37_1","volume-title":"Logical Analysis of Hybrid Systems: Proving Theorems for Complex Dynamics","author":"Platzer A."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-009-0079-8"},{"key":"e_1_2_1_39_1","volume-title":"Proc. of HSCC\u201907 (LNCS)","volume":"4416","author":"Podelski A."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.nahs.2010.05.010"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728606.2728615"},{"key":"e_1_2_1_42_1","volume-title":"Proc. of CAV\u201911 (LNCS)","volume":"6806","author":"Sankaranarayanan S."},{"key":"e_1_2_1_43_1","unstructured":"D. S\u0306iljak. 1978. Large-scale dynamic systems: stability and structure. North Holland.  D. S\u0306iljak. 1978. Large-scale dynamic systems: stability and structure. North Holland."},{"key":"e_1_2_1_44_1","volume-title":"NLTOOLBOX: A Library for Reachability Computation of Nonlinear Dynamical Systems. In Proc. of ATVA\u201913 (LNCS)","author":"Testylier R.","year":"2013"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.2337\/dc07-1967"},{"key":"e_1_2_1_46_1","volume-title":"IEEE Conf. on Decision and Control (CDC). IEEE Press.","author":"Zutshi A."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31424-7_27"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126522","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3126522","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3126522","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:01Z","timestamp":1750273501000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126522"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,27]]},"references-count":45,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3126522"],"URL":"https:\/\/doi.org\/10.1145\/3126522","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,27]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}