1. In a computing environment comprising at least one processor and at least one computer-readable storage media, a method for compiling a quantified formula into a non-deterministic program and controlling execution of a resulting non-deterministic program, the method comprising: providing a quantifier input parameter that decides whether an instance of a quantifier of the quantified formula holds; setting the quantifier input parameter to true; finding at least one quantifier instantiation that restricts possible values for the input parameter by performing a quantifier instantiation method, the quantifier instantiation method comprising: making a quantified assumption for the input parameter, wherein the quantified assumption has at least one pattern; partially evaluating the at least one pattern in the quantified assumption by run-time values of non-bound parameters; applying a maximal partial evaluation on the pattern to create a maximally partially evaluated pattern such that constant folding is applied to all sub-terms that do not contain any quantified variables; and at run-time, building a symbolic state of the program based on a symbolic representation of the current state of the program; labeling each node in the symbolic state with a corresponding concrete run-time value; enumerating the sub-terms that appear in the symbolic state; and matching the maximally partially evaluated pattern against the enumerated sub-terms; and setting the quantifier input parameter to false and non-deterministically finding a value for the bound variable of the quantifier such that the quantified formula does not hold for this value.
4. The method of claim 1 wherein non-deterministically finding a value for the bound variable of the quantifier such that the quantified formula does not hold comprises performing a second quantifier instantiation method wherein the second quantifier instantiation method comprises: making a quantified assumption as to the quantified input parameter where the quantified formula does not hold; partially evaluating a pattern in the quantified assumption by using run-time values of non-bound parameters where the quantifier does not hold; applying a maximal partial evaluation on the pattern, where the quantified formula does not hold, to create a maximally partially evaluated pattern such that constant folding is applied to all sub-terms that do not contain any quantified variables; and at run-time, building a symbolic state of the program, where the quantified formula does not hold, based on a symbolic representation of the current state of the program; labeling each node in the symbolic state of the program, where the quantified formula does not hold, with a corresponding concrete run-time value; enumerating the sub-terms that appear in the symbolic state of the program where the quantified formula does not hold; and matching the maximally partially evaluated pattern against the enumerated sub-terms.