2009 | OriginalPaper | Buchkapitel
Quantifier Elimination via Functional Composition
verfasst von : Jie-Hong R. Jiang
Erschienen in: Computer Aided Verification
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.