Philipp, T., & Rebola-Pardo, A. (2016). DRAT proofs for XOR reasoning. In L. Michael & A. Kakas (Eds.), Logics in Artificial Intelligence : 15th European Conference, JELIA 2016, Larnaca, Cyprus, November 9-11, 2016, Proceedings. Springer Cham. https://doi.org/10.1007/978-3-319-48758-8_27
JELIA: European Conference on Logics in Artificial Intelligence 2016
-
Event date:
9-Nov-2016 - 11-Nov-2016
-
Event place:
Larnaca, Cyprus
-
Number of Pages:
15
-
Publisher:
Springer Cham
-
Abstract:
Unsatisfiability proofs in the DRAT format became the de facto standard to increase the reliability of contemporary SAT solvers. We consider the problem of generating proofs for the XOR reasoning component in SAT solvers and propose two methods: direct translation transforms every XOR constraint addition inference into a DRAT proof, whereas T-translation avoids the exponential blow-up in direct translations by using fresh variables. T-translation produces DRAT proofs from Gaussian elimination records that are polynomial in the size of the input CNF formula. Experiments show that a combination of both approaches with a simple prediction method outperforms the BDD-based method.
en
Additional information:
The final publication is available via <a href="https://doi.org/10.1007/978-3-319-48758-8_27" target="_blank">https://doi.org/10.1007/978-3-319-48758-8_27</a>.
CC BY 4.0
