Computing Semi-algebraic Invariants for Polynomial Dynamical Systems

Abstract

In this paper, we consider an extended concept of invariant for polynomial dynamical system (PDS) with domain and initial condition, and establish a sound and complete criterion for checking semi-algebraic invariants (SAI) for such PDSs. The main idea is encoding relevant dynamical properties as conditions on the high order Lie derivatives of polynomials occurring in the SAI. A direct consequence of this criterion is a relatively complete method of SAI generation based on template assumption and semi-algebraic constraint solving. Relative completeness means if there is an SAI in the form of a predefined template, then our method can indeed find one using this template.

28 pages

Cited by in corpus (8)

• Exact Safety Verification of Hybrid Systems Based on Bilinear SOS Representation
• Barrier Certificates Revisited
• A Framework for Hybrid Systems with Denial-of-Service Security Attack
• A "Hybrid" Approach for Synthesizing Optimal Controllers of Hybrid Systems: A Case Study of the Oil Pump Industrial Example
• Abstraction of Elementary Hybrid Systems by Variable Transformation
• Compositional Hoare-style Reasoning about Hybrid CSP in the Duration Calculus
• Robust Non-termination Analysis of Numerical Software
• Exact Safety Verification of Interval Hybrid Systems Based on Symbolic-Numeric Computation