Computing semi-algebraic invariants for polynomial dynamical systems

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Liu, Jiang, Zhan, Naijun, Zhao, Hengjun
Format: Conference Proceeding
Language:English
Subjects:
Computing methodologies > Symbolic and algebraic manipulation > Symbolic and algebraic algorithms > Algebraic algorithms
Invariant
Mathematical model
Polynomial dynamical system
Polynomials
Safety
Semi-algebraic set
Software
Software and its engineering > Software creation and management > Software verification and validation > Formal software verification
Software and its engineering > Software organization and properties > Software functional properties > Formal methods
Trajectory
Vectors
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
DOI:10.1145/2038642.2038659