PARAMETRIC EQUATION SOLVING AND QUANTIFIER ELIMINATION IN FINITE FIELDS WITH THE CHARACTERISTIC SET METHOD

For a parametric algebraic system in finite fields, this paper presents a method for computing the cover and the refined cover based on the characteristic set method. From the cover, the author knows for what parametric values the system has solutions and at the same time presents the solutions in the form of proper chains. By the refined cover, the author gives a complete classification of the number of solutions for this system, that is, the author divides the parameter space into several disjoint components, and on every component the system has a fix number of solutions. Moreover, the author develops a method of quantifier elimination for first order formulas in finite fields.

A QUANTIFIER-ELIMINATION BASED HEURISTIC FOR AUTOMATICALLY GENERATING INDUCTIVE ASSERTIONS FOR PROGRAMS

A method using quantifier-elimination is proposed for automatically generating program invariants/inductive assertions. Given a program, inductive assertions, hypothesized as parameterized formulas in a theory, are associated with program locations. Parameters in inductive assertions are discovered by generating constraints on parameters by ensuring that an inductive assertion is indeed preserved by all execution paths leading to the associated location of the program. The method can be used to discover loop invariants-properties of variables that remain invariant at the entry of a loop. The parameterized formula can be successively refined by considering execution paths one by one; heuristics can be developed for determining the order in which the paths are considered. Initialization of program variables as well as the precondition and postcondition, if available, can also be used to further refine the hypothesized invariant. The method does not depend on the availability of the precondition and postcondition of a program. Constraints on parameters generated in this way are solved for possible values of parameters. If no solution is possible, this means that an invariant of the hypothesized form is not likely to exist for the loop under the assumptions/approximations made to generate the associated verification condition. Otherwise, if the parametric constraints are solvable, then under certain conditions on methods for generating these constraints, the strongest possible invariant of the hypothesized form can be generated from most general solutions of the parametric constraints. The approach is illustrated using the logical languages of conjunction of polynomial equations as well as Presburger arithmetic for expressing assertions.

A Survey on Algorithms for Computing Comprehensive Gröbner Systems and Comprehensive Gröbner Bases

Weispfenning in 1992 introduced the concepts of comprehensive Gr?bner system/basis of a parametric polynomial system, and he also presented an algorithm to compute them. Since then,this research ?eld has attracted much attention over the past several decades, and many effcient algorithms have been proposed. Moreover, these algorithms have been applied to many different ?elds,such as parametric polynomial equations solving, geometric theorem proving and discovering, quanti?er elimination, and so on. This survey brings together the works published between 1992 and 2018, and we hope that this survey is valuable for this research area.