  We consider the Quantifier Elimination (QE) problem for propositional CNF
formulas with existential quantifiers. QE plays a key role in formal
verification. Earlier, we presented an approach based on the following
observation. To perform QE, one just needs to add a set of clauses depending on
free variables that makes the quantified clauses (i.e. clauses with quantified
variables) redundant. To implement this approach, we introduced a branching
algorithm making quantified clauses redundant in subspaces and merging the
results of branches. To implement this algorithm we developed the machinery of
D-sequents. A D-sequent is a record stating that a quantified clause is
redundant in a specified subspace. Redundancy of a clause is a structural
property (i.e. it holds only for a subset of logically equivalent formulas as
opposed to a semantic property). So, re-using D-sequents is not as easy as
re-using conflict clauses in SAT-solving. In this paper, we address this
problem. We introduce a new definition of D-sequents that enables their
re-usability. We develop a theory showing under what conditions a D-sequent can
be safely re-used.
