We consider reasoning and minimization in systems of polynomial ordinary differential equations (ode's). The ring of multivariate polynomials is employed as a syntax for denoting system behaviours. We endow this set with a transition system structure based on the concept of Lie-derivative, thus inducing a notion of L-bisimulation. We prove that two states (variables) are L-bisimilar if and only if they correspond to the same solution in the ode's system. We then characterize L-bisimilarity algebraically, in terms of certain ideals in the polynomial ring that are invariant under Lie-derivation. This characterization allows us to develop a complete algorithm, based on building an ascending chain of ideals, for computing the largest L-bisimulation containing all valid identities that are instances of a user-specified template. A specific largest L-bisimulation can be used to build a reduced system of ode's, equivalent to the original one, but minimal among all those obtainable by linear aggregation of the original equations. A computationally less demanding approximate reduction and linearization technique is also proposed.
Ideas from Algebraic Geometry have been fruitfully applied also in Program Analysis. Relevant to our work is M " u ller-Olm and Seidl's @cite_22 , where an algorithm to compute all polynomial invariants up to a given degree of an imperative program is provided. Similarly to what we do, they reduce the core problem to a linear algebraic one. However, being the setting in @cite_22 discrete rather than continuous, the techniques employed there are otherwise quite different, mainly because: (a) the construction of the ideal chain is driven by the program's operational semantics, rather than by Lie derivatives; (b) the found polynomial invariants must be valid under initial program states, not just under the user specified one. If transferred to a continuous setting, condition (b) would lead in most cases to trivial invariants.
@cite_22
1971043610 39834257 1603048013 2109179224
This paper presents a method for automatically generating all polynomial invariants in simple loops. It is first shown that the set of polynomials serving as loop invariants has the algebraic structure of an ideal. Based on this connection, a fixpoint procedure using operations on ideals and Grobner basis constructions is proposed for finding all polynomial invariants. Most importantly, it is proved that the procedure terminates in at most m+1 iterations, where m is the number of program variables. The proof relies on showing that the irreducible components of the varieties associated with the ideals generated by the procedure either remain the same or increase their dimension at every iteration of the fixpoint procedure. This yields a correct and complete algorithm for inferring conjunctions of polynomial equalities as invariants. The method has been implemented in Maple using the Groebner package. The implementation has been used to automatically discover non-trivial invariants for several examples to illustrate the power of the technique. Geometric heuristics for the quantifier elimination approach presented by Kapur (2004) are investigated to automatically derive loop invariants expressing weakly relational numerical properties (such as l≤x≤h or l≤±x ±y≤h) for imperative programs. Such properties have been successfully used to analyze commercial software consisting of hundreds of thousands of lines of code (using for example, the Astree tool based on abstract interpretation framework proposed by Cousot and his group). The main attraction of the proposed approach is its much lower complexity in contrast to the abstract interpretation approach (O(n2) in contrast to O(n4), where n is the number of variables) with the ability to still generate invariants of comparable strength. This approach has been generalized to consider disjunctive invariants of the similar form, expressed using maximum function (such as max (x+a,y+b,z+c,d)≤max (x+e,y+f,z+g,h)), thus enabling automatic generation of a subclass of disjunctive invariants for imperative programs as well. We present a novel static analysis for approximating the algebraic relational semantics of imperative programs. Our method is based on abstract interpretation in the lattice of polynomial pseudo ideals of bounded degree – finite-dimensional vector spaces of polynomials of bounded degree which are closed under bounded degree products. For a fixed bound, the space complexity of our approach and the iterations required to converge on fixed points are bounded by a polynomial in the number of program variables. Nevertheless, for several programs taken from the literature on non-linear polynomial invariant generation, our analysis produces results that are as precise as those produced by more heavy-weight Grobner basis methods. We propose a static analysis for computing polynomial invariants for imperative programs. The analysis is derived from an abstract interpretation of a backwards semantics, and computes pre-conditions for equalities like g=0 to hold at the end of execution. A distinguishing feature of the technique is that it computes polynomial loop invariants without resorting to Grobner base computations. The analysis uses remainder computations over parameterized polynomials in order to handle conditionals and loops efficiently. The algorithm can analyse and find a large majority of loop invariants reported previously in the literature, and executes significantly faster than implementations using Grobner bases.