Aligning CNF- and equivalence-reasoning

Conference paper (2005)

Authors

M.J.H. Heule Old - EWI Ch. Optimization Technology
H. van Maaren Software Technology
Research Group
Old - EWI Ch. Optimization Technology
More Info
expand_more

Published Date

2005

Language

Undefined/Unknown

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Research Group

Old - EWI Ch. Optimization Technology

Abstract

Structural logical formulas sometimes yield a substantial fraction of so called equivalence clauses after translation to CNF. Probably the best known example of this is the parity-family. Large instances of such CNF formulas cannot be solved in reasonable time if no detection of, and extra reasoning with, these clauses is incorporated. That is, in solving these formulas, there is a more or less separate algorithmic device dealing with the equivalence clauses, called equivalence reasoning, and another dealing with the remaining clauses. In this paper we propose a way to align these two reasoning devices by introducing parameters for which we establish optimal values over a variety of existing benchmarks. We obtain a truly convincing speed-up in solving such formulas with respect to the best solving methods existing so far.