{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:43:54Z","timestamp":1742913834654,"version":"3.40.3"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030324087"},{"type":"electronic","value":"9783030324094"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-32409-4_15","type":"book-chapter","created":{"date-parts":[[2019,10,27]],"date-time":"2019-10-27T20:03:00Z","timestamp":1572206580000},"page":"236-252","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Probably Approximate Safety Verification of Hybrid Dynamical Systems"],"prefix":"10.1007","author":[{"given":"Bai","family":"Xue","sequence":"first","affiliation":[]},{"given":"Martin","family":"Fr\u00e4nzle","sequence":"additional","affiliation":[]},{"given":"Hengjun","family":"Zhao","sequence":"additional","affiliation":[]},{"given":"Naijun","family":"Zhan","sequence":"additional","affiliation":[]},{"given":"Arvind","family":"Easwaran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,28]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R.: Formal verification of hybrid systems. In: EMSOFT 2011, pp. 273\u2013278. IEEE (2011)","DOI":"10.1145\/2038642.2038685"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/3-540-57318-6_30","volume-title":"Hybrid Systems","author":"R Alur","year":"1993","unstructured":"Alur, R., Courcoubetis, C., Henzinger, T.A., Ho, P.-H.: Hybrid automata: an algorithmic approach to the specification and verification of hybrid systems. In: Grossman, R.L., Nerode, A., Ravn, A.P., Rischel, H. (eds.) HS 1991-1992. LNCS, vol. 736, pp. 209\u2013229. Springer, Heidelberg (1993). \n                      https:\/\/doi.org\/10.1007\/3-540-57318-6_30"},{"issue":"3","key":"15_CR3","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1006\/jcss.1998.1601","volume":"57","author":"E Asarin","year":"1998","unstructured":"Asarin, E., Maler, O.: Achilles and the tortoise climbing up the arithmetical hierarchy. J. Comput. Syst. Sci. 57(3), 389\u2013398 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"15_CR4","doi-asserted-by":"publisher","first-page":"3427","DOI":"10.1137\/090773490","volume":"20","author":"GC Calafiore","year":"2010","unstructured":"Calafiore, G.C.: Random convex programs. SIAM J. Optim. 20(6), 3427\u20133464 (2010)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"15_CR5","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s10957-010-9754-6","volume":"148","author":"MC Campi","year":"2011","unstructured":"Campi, M.C., Garatti, S.: A sampling-and-discarding approach to chance-constrained optimization: feasibility and optimality. J. Optim. Theory Appl. 148(2), 257\u2013280 (2011)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"15_CR6","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.arcontrol.2009.07.001","volume":"33","author":"MC Campi","year":"2009","unstructured":"Campi, M.C., Garatti, S., Prandini, M.: The scenario approach for systems and control design. Annu. Rev. Control 33(2), 149\u2013157 (2009)","journal-title":"Annu. Rev. Control"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.jsc.2016.07.010","volume":"80","author":"L Dai","year":"2017","unstructured":"Dai, L., Gan, T., Xia, B., Zhan, N.: Barrier certificates revisited. J. Symb. Comput. 80, 62\u201386 (2017)","journal-title":"J. Symb. Comput."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Djaballah, A.: Computation of barrier certificates for dynamical hybrids systems using interval analysis. Universit\u00e9 Paris-Saclay (2017)","DOI":"10.1016\/j.automatica.2016.12.013"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Egyed, A.: Invited talk: a roadmap for engineering safe and secure cyber-physical systems. In: MEDI 2018, pp. 113\u2013114 (2018)","DOI":"10.1007\/978-3-030-02852-7_10"},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-48168-0_10","volume-title":"Computer Science Logic","author":"M Fr\u00e4nzle","year":"1999","unstructured":"Fr\u00e4nzle, M.: Analysis of hybrid systems: an ounce of realism can save an infinity of states. In: Flum, J., Rodriguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol. 1683, pp. 126\u2013139. Springer, Heidelberg (1999). \n                      https:\/\/doi.org\/10.1007\/3-540-48168-0_10"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-319-22975-1_7","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"M Fr\u00e4nzle","year":"2015","unstructured":"Fr\u00e4nzle, M., Gerwinn, S., Kr\u00f6ger, P., Abate, A., Katoen, J.-P.: Multi-objective parameter synthesis in probabilistic hybrid systems. In: Sankaranarayanan, S., Vicario, E. (eds.) FORMATS 2015. LNCS, vol. 9268, pp. 93\u2013107. Springer, Cham (2015). \n                      https:\/\/doi.org\/10.1007\/978-3-319-22975-1_7"},{"key":"15_CR12","first-page":"209","volume":"1","author":"M Fr\u00e4nzle","year":"2007","unstructured":"Fr\u00e4nzle, M., Herde, C., Teige, T., Ratschan, S., Schubert, T.: Efficient solving of large non-linear arithmetic constraint systems with complex boolean structure. J. Satisf. Boolean Model. Comput. 1, 209\u2013236 (2007)","journal-title":"J. Satisf. Boolean Model. Comput."},{"key":"15_CR13","unstructured":"Fr\u00e4nzle, M., Shirmohammadi, M., Swaminathan, M., Worrell, J.: Costs and rewards in priced timed automata. In: ICALP 2018, pp. 125:1\u2013125:14 (2018)"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Gao, S., Avigad, J., Clarke, E.M.: Delta-decidability over the reals. In: LICS 2012, pp. 305\u2013314 (2012)","DOI":"10.1109\/LICS.2012.41"},{"key":"15_CR15","unstructured":"Haussler, D.: Probably approximately correct learning. Computer Research Laboratory, University of California, Santa Cruz (1990)"},{"issue":"4","key":"15_CR16","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1137\/080730287","volume":"51","author":"D Henrion","year":"2009","unstructured":"Henrion, D., Lasserre, J.B., Savorgnan, C.: Approximate volume and integration for basic semialgebraic sets. SIAM Rev. 51(4), 722\u2013743 (2009)","journal-title":"SIAM Rev."},{"issue":"1","key":"15_CR17","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1006\/jcss.1998.1581","volume":"57","author":"TA Henzinger","year":"1998","unstructured":"Henzinger, T.A., Kopke, P.W., Puri, A., Varaiya, P.: What\u2019s decidable about hybrid automata? J. Comput. Syst. Sci. 57(1), 94\u2013124 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"301","key":"15_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"issue":"5","key":"15_CR19","first-page":"186:1","volume":"16","author":"C Huang","year":"2017","unstructured":"Huang, C., Chen, X., Lin, W., Yang, Z., Li, X.: Probabilistic safety verification of stochastic hybrid systems using barrier certificates. ACM Trans. Embed. Comput. Syst. 16(5), 186:1\u2013186:19 (2017)","journal-title":"ACM Trans. Embed. Comput. Syst."},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Kong, H., Bogomolov, S., Schilling, C., Jiang, Y., Henzinger, T.A.: Safety verification of nonlinear hybrid systems based on invariant clusters. In: HSCC 2017, pp. 163\u2013172. ACM (2017)","DOI":"10.1145\/3049797.3049814"},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-642-39799-8_17","volume-title":"Computer Aided Verification","author":"H Kong","year":"2013","unstructured":"Kong, H., He, F., Song, X., Hung, W.N.N., Gu, M.: Exponential-condition-based barrier certificate generation for safety verification of hybrid systems. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 242\u2013257. Springer, Heidelberg (2013). \n                      https:\/\/doi.org\/10.1007\/978-3-642-39799-8_17"},{"issue":"5","key":"15_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-013-4961-z","volume":"57","author":"W Lin","year":"2014","unstructured":"Lin, W., Wu, M., Yang, Z., Zeng, Z.: Exact safety verification of hybrid systems using sums-of-squares representation. Sci. China Inf. Sci. 57(5), 1\u201313 (2014)","journal-title":"Sci. China Inf. Sci."},{"key":"15_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-540-73368-3_47","volume-title":"Computer Aided Verification","author":"T Nahhal","year":"2007","unstructured":"Nahhal, T., Dang, T.: Test coverage for continuous and hybrid systems. In: Damm, W., Hermanns, H. (eds.) CAV 2007. LNCS, vol. 4590, pp. 449\u2013462. Springer, Heidelberg (2007). \n                      https:\/\/doi.org\/10.1007\/978-3-540-73368-3_47"},{"key":"15_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-24743-2_32","volume-title":"Hybrid Systems: Computation and Control","author":"S Prajna","year":"2004","unstructured":"Prajna, S., Jadbabaie, A.: Safety verification of hybrid systems using barrier certificates. In: Alur, R., Pappas, G.J. (eds.) HSCC 2004. LNCS, vol. 2993, pp. 477\u2013492. Springer, Heidelberg (2004). \n                      https:\/\/doi.org\/10.1007\/978-3-540-24743-2_32"},{"key":"15_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-319-65765-3_17","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"S Ratschan","year":"2017","unstructured":"Ratschan, S.: Simulation based computation of certificates for safety of dynamical systems. In: Abate, A., Geeraerts, G. (eds.) FORMATS 2017. LNCS, vol. 10419, pp. 303\u2013317. Springer, Cham (2017). \n                      https:\/\/doi.org\/10.1007\/978-3-319-65765-3_17"},{"issue":"1","key":"15_CR26","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/1210268.1210276","volume":"6","author":"S Ratschan","year":"2007","unstructured":"Ratschan, S., She, Z.: Safety verification of hybrid systems by constraint propagation-based abstraction refinement. ACM Trans. Embed. Comput. S. 6(1), 8 (2007)","journal-title":"ACM Trans. Embed. Comput. S."},{"issue":"7","key":"15_CR27","doi-asserted-by":"publisher","first-page":"4377","DOI":"10.1137\/090749955","volume":"48","author":"S Ratschan","year":"2010","unstructured":"Ratschan, S., She, Z.: Providing a basin of attraction to a target region of polynomial systems by computation of lyapunov-like functions. SIAM J. Control Optim. 48(7), 4377\u20134394 (2010)","journal-title":"SIAM J. Control Optim."},{"key":"15_CR28","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1080\/03081089508818341","volume":"38","author":"JI Rohn","year":"1994","unstructured":"Rohn, J.I., Kreslova, J.: Linear interval inequalities. Linear Multilinear Algebra 38, 79\u201382 (1994)","journal-title":"Linear Multilinear Algebra"},{"key":"15_CR29","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan, S., Chen, X., \u00c1brah\u00e1m, E.: Lyapunov function synthesis using Handelman representations. In: NOLCOS 2013, pp. 576\u2013581 (2013)","DOI":"10.3182\/20130904-3-FR-2041.00198"},{"key":"15_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/978-3-319-25141-7_2","volume-title":"Cyber Physical Systems. Design, Modeling, and Evaluation","author":"S Schupp","year":"2015","unstructured":"Schupp, S., et al.: Current challenges in the verification of hybrid systems. In: Berger, C., Mousavi, M.R. (eds.) CyPhy 2015. LNCS, vol. 9361, pp. 8\u201324. Springer, Cham (2015). \n                      https:\/\/doi.org\/10.1007\/978-3-319-25141-7_2"},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"Shmarov, F., Zuliani, P.: ProbReach: verified probabilistic delta-reachability for stochastic hybrid systems. In: HSCC 2015, pp. 134\u2013139 (2015)","DOI":"10.1145\/2728606.2728625"},{"key":"15_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/978-3-319-95582-7_25","volume-title":"Formal Methods","author":"A Sogokon","year":"2018","unstructured":"Sogokon, A., Ghorbal, K., Tan, Y.K., Platzer, A.: Vector barrier certificates and comparison systems. In: Havelund, K., Peleska, J., Roscoe, B., de Vink, E. (eds.) FM 2018. LNCS, vol. 10951, pp. 418\u2013437. Springer, Cham (2018). \n                      https:\/\/doi.org\/10.1007\/978-3-319-95582-7_25"},{"key":"15_CR33","doi-asserted-by":"crossref","unstructured":"Xue, B. Fr\u00e4nzle, M., Zhan, N.: Inner-approximating reachable sets for polynomial systems with time-varying uncertainties. IEEE Trans. Autom. Control (2019)","DOI":"10.1109\/TAC.2019.2923049"},{"key":"15_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/978-3-319-41528-4_25","volume-title":"Computer Aided Verification","author":"B Xue","year":"2016","unstructured":"Xue, B., She, Z., Easwaran, A.: Under-approximating backward reachable sets by polytopes. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9779, pp. 457\u2013476. Springer, Cham (2016). \n                      https:\/\/doi.org\/10.1007\/978-3-319-41528-4_25"},{"issue":"10","key":"15_CR35","doi-asserted-by":"publisher","first-page":"5185","DOI":"10.1109\/TAC.2017.2694351","volume":"62","author":"B Xue","year":"2017","unstructured":"Xue, B., She, Z., Easwaran, A.: Underapproximating backward reachable sets by semialgebraic sets. IEEE Trans. Autom. Control 62(10), 5185\u20135197 (2017)","journal-title":"IEEE Trans. Autom. Control"},{"key":"15_CR36","doi-asserted-by":"crossref","unstructured":"Xue, B., Wang, Q., Zhan, N., Fr\u00e4nzle, M.: Robust invariant sets generation for state-constrained perturbed polynomial systems. In: HSCC 2019, pp. 128\u2013137 (2019)","DOI":"10.1145\/3302504.3311810"},{"issue":"11","key":"15_CR37","doi-asserted-by":"publisher","first-page":"2768","DOI":"10.1109\/TCAD.2018.2858383","volume":"37","author":"Y Zhang","year":"2018","unstructured":"Zhang, Y., Yang, Z., Lin, W., Zhu, H., Chen, X., Li, X.: Safety verification of nonlinear hybrid systems based on bilinear programming. IEEE Trans. CAD Integr. Circuits Syst. 37(11), 2768\u20132778 (2018)","journal-title":"IEEE Trans. CAD Integr. Circuits Syst."},{"key":"15_CR38","doi-asserted-by":"crossref","unstructured":"Zuliani, P., Platzer, A., Clarke, E.M.: Bayesian statistical model checking with application to simulink\/stateflow verification. In: HSCC 2010, pp. 243\u2013252 (2010)","DOI":"10.21236\/ADA531406"}],"container-title":["Lecture Notes in Computer Science","Formal Methods and Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-32409-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,2]],"date-time":"2019-11-02T04:54:59Z","timestamp":1572670499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-32409-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030324087","9783030324094"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-32409-4_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"28 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICFEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Formal Engineering Methods","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shenzhen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 November 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 November 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"icfem2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/csse.szu.edu.cn\/icfem2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"94","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}