Computing semi-algebraic invariants for polynomial dynamical systems

Abstract

In this paper, we consider an extended concept of invariant for polynomial dynamical systems (PDSs) with domain and initial condition, and establish a sound and complete criterion for checking semi-algebraic invariants (SAIs) 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.