Abstract | ||
---|---|---|
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. |
Year | Venue | Field |
---|---|---|
2018 | arXiv: Logic in Computer Science | Quantifier elimination,Logical equivalence,Subspace topology,Free variables and bound variables,Semantic property,Algorithm,Linear subspace,Theoretical computer science,Redundancy (engineering),Mathematics,Formal verification |
DocType | Volume | Citations |
Journal | abs/1810.00160 | 0 |
PageRank | References | Authors |
0.34 | 2 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Eugene Goldberg | 1 | 25 | 8.01 |