Generating Semi-Algebraic Invariants for Non-Autonomous Polynomial Hybrid Systems

Hybrid systems are dynamical systems with interacting discrete computation and continuous physical processes, which have become more common, more indispensable, and more complicated in our modern life. Particularly, many of them are safety-critical, and therefore are required to meet a critical safety standard. Invariant generation plays a central role in the verification and synthesis of hybrid systems. In the previous work, the fourth author and his coauthors gave a necessary and sufficient condition for a semi-algebraic set being an invariant of a polynomial autonomous dynamical system, which gave a confirmative answer to the open problem. In addition, based on which a complete algorithm for generating all semi-algebraic invariants of a given polynomial autonomous hybrid system with the given shape was proposed. This paper considers how to extend their work to non-autonomous dynamical and hybrid systems. Non-autonomous dynamical and hybrid systems are with inputs, which are very common in practice; in contrast, autonomous ones are without inputs. Furthermore, the authors present a sound and complete algorithm to verify semi-algebraic invariants for non-autonomous polynomial hybrid systems. Based on which, the authors propose a sound and complete algorithm to generate all invariants with a pre-defined template.

Safety Verification of Semi-Algebraic Dynamical Systems via Inductive Invariant

To verify the safety of nonlinear dynamical systems based on inductive invariants, key issues include defining the most complete inductive condition and discovering an inductive invariant that satisfies the specified inductive condition. In this paper, to lay a solid foundation for future research into the safety verification of semi- algebraic dynamical systems, we first establish a formal framework for evaluating the quality of continuous inductive conditions. In addition, we propose a new complete and computable inductive condition for verifying the safety of semi-algebraic dynamical systems. Compared with the existing complete and computable inductive condition, this new inductive condition can be easily adapted to achieve a set of sufficient inductive conditions with different level of conservativeness and computational complexity, which provides us with a means to trade off between the verification power and complexity. These inductive conditions can be solved by quantifier elimination and SMT solvers.

SEMI-ALGEBRAICALLY CONNECTED COMPONENTS OF MINIMUM POINTS OF A POLYNOMIAL FUNCTION

In a recent article, the authors provided an effective algorithm for both computing the global infimum of f and deciding whether or not the infimum of f is attained, where f is a multivariate polynomial over the field R of real numbers. As a complement, the authors investigate the semi- algebraically connected components of minimum points of a polynomial function in this paper. For a given multivariate polynomial f over R, it is shown that the above-mentioned algorithm can find at least one point in each semi-algebraically connected component of minimum points of f whenever f has its global minimum.