Optimization to prune the instantiations search space

[bestchai]

The optimization in Issue 26 concerns reducing computation time for checking an instantiation. An orthogonal optimization is to prune instantiations (i.e., not checking some sub-set of instantiations at all) based on previously checked results.

Consider the formula visualized in Issue 26: i.e., the formula "s,t without z responds to p after q until r", in LTL: G (q -> (p -> (!r U (s & !r & !z & X((!r & !z) U t)))) U (r | G(p -> (s & !z & X(!z U t))))).

In the tree for this formula, for the top-level OR node, there is a left-or branch and a right-or branch.

Consider an instantiation of this formula that is checked for some binding of the variables in the formula: p,q,r,s,t,z. If this instantiation has a sub-tree evaluation where the left-or sub-tree is TRUE (with q as the only atomic proposition), then it doesn't matter what p,r,s,t,z are bound to -- the right-or tree has no effect on the evaluation of a formula instance that uses the same binding for q. That is, we can prune the search space by removing all instances that have the same q binding and emitting them as valid.

Generalizing this observation is the challenging aspect of this issue. One way to programmatically do this is to (1) consider a sub-set of the bindings for a formula instance, and (2) set the other bindings to evaluate to FALSE. Then, (3) if the resulting formula instance evaluates to TRUE, then we can prune the space of instances using the sub-set of bindings selected in (1) and emit these as VALID.

Note that a dual optimization is also possible. In this case the general version would look like: (1) consider a sub-set of the bindings for a formula instance, and (2) set the other bindings to evaluate to TRUE (not FALSE as in above). Then, (3) if the resulting formula instance evaluates to FALSE (not TRUE, as in above), then we can prune the space of instances using the sub-set of bindings selected in (1) and emit these as INVALID (not VALID, as above). That is, in the dual, the sub-set of bindings makes the formula always evaluate to FALSE, so we can prune the search space since we know we can never make the complete bindings function make a formula instance evaluate to TRUE.

[Issue created by bestchai: 2014-08-18]