Abstract
ZRes is a propositional prover based on the original procedure of Davis and Putnam, as opposed to its modified version of Davis, Logeman and Loveland, on which most of the current efficient SAT provers are based. On some highly structured SAT instances, such as the well known Pigeon Hole and Urquhart problems, both proved hard for resolution, ZRes performs very well and surpasses all classical SAT provers by an order of magnitude.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bryant, R.E.: Graph - based algorithms for boolean function manipulation. IEEE Trans. on Comp. 35(8), 677–691 (1986)
Chatalic, P., Simon, L.: Davis and putnam 40 years later: a first experimentation. Technical Report 1237, LRI, Orsay, France (2000), submitted to the Journal of Automated Reasoning
Davis, M., Putnam, H.: A computing procedure for quantification theory. Journal of the ACM, 201–215 (1960)
de Kleer, J.: An improved incremental algorithm for generating prime implicates. In: AAAI 1992, pp. 780–785 (1992)
Dechter, R., Rish, I.: Directional resolution: The Davis–Putnam procedure, revisited. In: Proceedings of KR 1994, pp. 134–145 (1994)
The DIMACS challenge benchmarks, ftp://ftp.rutgers.dimacs.edu/challenges/sat
Drechsler, R., Becker, B.: Binary Decision Diagram: Theory and Implementation. Kluwer Academic Publisher, Dordrecht (1998)
Dubois, O.: Can a very simple algorithm be efficient for SAT?, ftp://ftp.dimacs.rutgers.edu/pub/challenges/sat/contributed/dubois
Galil, Z.: On the complexity of regular resolution and the Davis–Putnam procedure. Theorical Computer Science 4, 23–46 (1977)
Haken, A.: The intractability of resolution. Theorical Computer Science 39, 297–308 (1985)
Logeman, G., Davis, M., Loveland, D.: A machine program for theorem-proving. Communications of the ACM, 394–397 (1962)
Minato, S.: Zero-suppressed bdds for set manipulation in combinatorial problems. In: 30th ACM/IEEE Design Automation Conference (1993)
Somenzy, F.: Cudd release 2.3.0., http://bessie.colorado.edu/~fabio
Urquhart, A.: Hard examples for resolution. Journal of the ACM 34, 209–219 (1987)
Zhang, H.: SATO: An efficient propositional prover. In: McCune, W. (ed.) CADE 1997. LNCS, vol. 1249, pp. 272–275. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chatalic, P., Simon, L. (2000). ZRes: The Old Davis–Putnam Procedure Meets ZBDD. In: McAllester, D. (eds) Automated Deduction - CADE-17. CADE 2000. Lecture Notes in Computer Science(), vol 1831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10721959_35
Download citation
DOI: https://doi.org/10.1007/10721959_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67664-5
Online ISBN: 978-3-540-45101-3
eBook Packages: Springer Book Archive