2009 | OriginalPaper | Chapter
Quantifier Elimination via Functional Composition
Author : Jie-Hong R. Jiang
Published in: Computer Aided Verification
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper poses the following basic question: Given a quantified Boolean formula ∃
x
.
ϕ
, what should a function/formula
f
be such that substituting
f
for
x
in
ϕ
yields a logically equivalent quantifier-free formula? Its answer leads to a solution to quantifier elimination in the Boolean domain, alternative to the conventional approach based on formula expansion. Such a composite function can be effectively derived using symbolic techniques and further simplified for practical applications. In particular, we explore Craig interpolation for scalable computation. This compositional approach to quantifier elimination is analyzably superior to the conventional one under certain practical assumptions. Experiments demonstrate the scalability of the approach. Several large problem instances unsolvable before can now be resolved effectively. A generalization to first-order logic characterizes a composite function’s complete flexibility, which awaits further exploitation to simplify quantifier elimination beyond the propositional case.