We present a method for the synthesis of polynomial lasso programs. These programs consist of a program stem, a set of transitions, and an exit condition, all in the form of algebraic assertions (conjunctions of polynomial equalities). Central to this approach is the discovery of non-linear (algebraic) loop invariants. We extend Sankaranarayanan, Sipma, and Manna's template-based approach and prove a completeness criterion. We perform program synthesis by generating a constraint whose solution is a synthesized program together with a loop invariant that proves the program's correctness. This constraint is non-linear and is passed to an SMT solver. Moreover, we can enforce the termination of the synthesized program with the support of test cases.
@cite_19: In this paper, we present methods for checking and inferring all valid polynomial relations in Z2w . In contrast to the infinite field Q, Z2w is finite and hence allows for finitely many polynomial functions only. In this paper we show, that checking the validity of a polynomial invariant over Z2w is, though decid- able, only PSPACE-complete. Apart from the impracticable algorithm for the theoretical upper bound, we present a feasible algorithm for verifying polyno- mial invariants over Z2w which runs in polynomial time if the number of program variables is bounded by a constant. In this case, we also obtain a polynomial-time algorithm for inferring all polynomial relations. In general, our approach provides us with a feasible algorithm to infer all polynomial invariants up to a low degree.
@cite_18: Several optimizations of programs can be performed when in certain regions of a program equality relationships hold between a linear combination of the variables of the program and a constant. This paper presents a practical approach to detecting these relationships by considering the problem from the viewpoint of linear algebra. Key to the practicality of this approach is an algorithm for the calculation of the "sum" of linear subspaces.
@cite_14: We present two automatic program analyses. The first analysis checks if a given polynomial relation holds among the program variables whenever control reaches a given program point. It fully interprets assignment statements with polynomial expressions on the right-hand side and polynomial disequality guards. Other assignments are treated as non-deterministically assigning any value and guards that are not polynomial disequalities are ignored. The second analysis extends this checking procedure. It computes the set of all polynomial relations of an arbitrary given form that are valid at a given target program point. It is also complete up to the abstraction described above.
The automatic discovery of polynomial invariants for imperative programs has received a lot of attention in recent years. Müller-Olm and Seidl generate invariant polynomial equalities of bounded degree by backwards propagation @cite_14 . This can be seen as an extension to Karr's algorithm @cite_18 , which uses only linear arithmetic. Seidl, Flexeder and Petter apply the backwards-propagation method to programs over machine integers, i.e., programs whose variables range over the domain @math @cite_19 .