@inproceedings{9242e2da498b437bbb70376694ad9724,
title = "A linear programming relaxation based approach for generating barrier certificates of hybrid systems",
abstract = "This paper presents a linear programming (LP) relaxation based approach for generating polynomial barrier certificates for safety verification of semi-algebraic hybrid systems. The key idea is to introduce an LP relaxation to encode the set of nonnegativity constraints derived from the conditions of the associated barrier certificates and then resort to LP solvers to find the solutions. The most important benefit of the LP relaxation based approach is that it possesses a much lower computational complexity and hence can be solved very efficiently, which is demonstrated by the theoretical analysis on complexity as well as the experiment on a set of examples gathered from the literature. As far as we know, it is the first method that enables LP relaxation based polynomial barrier certificate generation.",
keywords = "Barrier certificates, Formal verification, Hybrid systems, Linear programming relaxation",
author = "Zhengfeng Yang and Chao Huang and Xin Chen and Wang Lin and Zhiming Liu",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 21st International Symposium on Formal Methods, FM 2016 ; Conference date: 09-11-2016 Through 11-11-2016",
year = "2016",
doi = "10.1007/978-3-319-48989-6\_44",
language = "英语",
isbn = "9783319489889",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "721--738",
editor = "Constance Heitmeyer and Anna Philippou and Stefania Gnesi and John Fitzgerald",
booktitle = "FM 2016",
address = "德国",
}