article

Solving SAT and SAT Modulo Theories: From an abstract Davis--Putnam--Logemann--Loveland procedure to DPLL(T)

Authors:

Robert Nieuwenhuis,

Albert Oliveras,

Cesare TinelliAuthors Info & Claims

Journal of the ACM (JACM), Volume 53, Issue 6

Pages 937 - 977

https://doi.org/10.1145/1217856.1217859

Published: 01 November 2006 Publication History

Abstract

We first introduce Abstract DPLL, a rule-based formulation of the Davis--Putnam--Logemann--Loveland (DPLL) procedure for propositional satisfiability. This abstract framework allows one to cleanly express practical DPLL algorithms and to formally reason about them in a simple way. Its properties, such as soundness, completeness or termination, immediately carry over to the modern DPLL implementations with features such as backjumping or clause learning.We then extend the framework to Satisfiability Modulo background Theories (SMT) and use it to model several variants of the so-called lazy approach for SMT. In particular, we use it to introduce a few variants of a new, efficient and modular approach for SMT based on a general DPLL(X) engine, whose parameter X can be instantiated with a specialized solver Solver_T for a given theory T, thus producing a DPLL(T) system. We describe the high-level design of DPLL(X) and its cooperation with Solver_T, discuss the role of theory propagation, and describe different DPLL(T) strategies for some theories arising in industrial applications.Our extensive experimental evidence, summarized in this article, shows that DPLL(T) systems can significantly outperform the other state-of-the-art tools, frequently even in orders of magnitude, and have better scaling properties.

References

[1]

Alur, R. 1999. Timed automata. In Proceedings of the 11th International Conference on Computer Aided Verification (CAV'99) (Trento, Italy), N. Halbwachs and D. Peled, Eds. Lecture Notes in Computer Science, vol. 1633. Springer-Verlag, New York, 8--22.]]

Digital Library

[2]

Armando, A., Castellini, C., and Giunchiglia, E. 2000. SAT-based procedures for temporal reasoning. In Proceedings of the 5th European Conference on Planning (Durham, UK), S. Biundo and M. Fox, Eds. Lecture Notes in Computer Science, vol. 1809. Springer-Verlag, New York, 97--108.]]

Digital Library

[3]

Armando, A., Castellini, C., Giunchiglia, E., and Maratea, M. 2004. A SAT-based decision procedure for the Boolean combination of difference constraints. In Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT 2004). Lecture Notes in Computer Science. Springer-Verlag, New York.]]

[4]

Audemard, G., Bertoli, P., Cimatti, A., Kornilowicz, A., and Sebastiani, R. 2002. A SAT based approach for solving formulas over Boolean and linear mathematical propositions. In Proceedings of the CADE-18. Lecture Notes in Computer Science, vol. 2392. Springer-Verlag, New York, 195--210.]]

Digital Library

[5]

Ball, T., Cook, B., Lahiri, S. K., and Zhang, L. 2004. Zapato: Automatic theorem proving for predicate abstraction refinement. In Proceedings of the 16th International Conference on Computer Aided Verification (CAV'04) (Boston, MA). R. Alur and D. Peled, Eds. Lecture Notes in Computer Science, vol. 3114. Springer-Verlag, New York. 457--461.]]

[6]

Barrett, C., de Moura, L., and Stump, A. 2005. SMT-COMP: Satisfiability modulo theories competition. In Proceedings of the 17th International Conference on Computer Aided Verification, K. Etessami and S. Rajamani, Eds. Lecture Notes in Computer Science, vol. 3576. Springer-Verlag, New York, 20--23. (See www.csl.sri.com/users/demoura/smt-comp.)]]

Digital Library

[7]

Barrett, C., Dill, D., and Stump, A. 2002. Checking satisfiability of first-order formulas by incremental translation into SAT. In Proceedings of the 14th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 2404. Springer-Verlag, New York.]]

Digital Library

[8]

Barrett, C., Dill, D. L., and Levitt, J. 1996. Validity checking for combinations of theories with equality. In Proceedings of the 1st International Conference on Formal Methods in Computer Aided Design. Lecture Notes in Computer Science, vol. 1166. Springer-Verlag, New York, 187--201.]]

Digital Library

[9]

Barrett, C. W. 2003. Checking validity of quantifier-free formulas in combinations of first-order theories. Ph.D. dissertation. Stanford University, Stanford, CA.]]

[10]

Barrett, C. W., and Berezin, S. 2004. CVC lite: A new implementation of the cooperating validity checker. In Proceedings of the 16th International Conference on Computer Aided Verification (CAV'04) (Boston, MA). R. Alur and D. Peled, Eds. Lecture Notes in Computer Science, vol. 3114. Springer-Verlag, New York, 515--518.]]

[11]

Bayardo, R. J. J., and Schrag, R. C. 1997. Using CSP look-back techniques to solve real-world SAT instances. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI'97) (Providence, RI), 203--208.]]

[12]

Beame, P., Kautz, H., and Sabharwal, A. 2003. On the power of clause learning. In Proceedings of IJCAI-03, 18th International Joint Conference on Artificial Intelligence (Acapulco, MX).]]

[13]

Bonet, M. L., Esteban, J. L., Galesi, N., and Johannsen, J. 2000. On the relative complexity of resolution refinements and cutting planes proof systems. SIAM J. Comput. 30, 5, 1462--1484.]]

Digital Library

[14]

Bozzano, M., Bruttomesso, R., Cimatti, A., Junttila, T. V. Rossum, P., Schulz, S., and Sebastiani, R. 2005. An incremental and layered procedure for the satisfiability of linear arithmetic logic. In Tools and Algorithms for the Construction and Analysis of Systems, 11th International Conference (TACAS). Lecture Notes in Computer Science, vol. 3440. Springer-Verlag, New York, 317--333.]]

Digital Library

[15]

Bryant, R., German, S., and Velev, M. 2001. Processor verification using efficient reductions of the logic of uninterpreted functions to propositional logic. ACM Trans. Computational Logic 2, 1, 93--134.]]

Digital Library

[16]

Bryant, R., Lahiri, S., and Seshia, S. 2002. Modeling and verifying systems using a logic of counter arithmetic with lambda expressions and uninterpreted functions. In Proceedings of the 14th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 2404. Springer-Verlag, New York.]]

Digital Library

[17]

Bryant, R. E., and Velev, M. N. 2002. Boolean satisfiability with transitivity constraints. ACM Trans. Computational Logic 3, 4, 604--627.]]

Digital Library

[18]

Burch, J. R., and Dill, D. L. 1994. Automatic verification of pipelined microprocessor control. In Proceedings of the 6th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 818. Springer-Verlag, New York. 68--80.]]

Digital Library

[19]

Davis, M., Logemann, G., and Loveland, D. 1962. A machine program for theorem-proving. Commun. ACM 5, 7, 394--397.]]

Digital Library

[20]

Davis, M., and Putnam, H. 1960. A computing procedure for quantification theory. J ACM 7, 201--215.]]

Digital Library

[21]

de Moura, L., and Rueß, H. 2002. Lemmas on demand for satisfiability solvers. In Proceedings of the 5th International Symposium on the Theory and Applications of Satisfiability Testing (SAT'02). 244--251.]]

[22]

de Moura, L., and Ruess, H. 2004. An experimental evaluation of ground decision procedures. In Proceedings of the 16th International Conference on Computer Aided Verification (CAV'04) (Boston, MA). R. Alur and D. Peled, Eds. Lecture Notes in Computer Science, vol. 3114. Springer-Verlag, New York, 162--174.]]

[23]

de Moura, L., Rueß, H., and Shankar, N. 2004. Justifying equality. In Proceedings of the 2nd Workshop on Pragmatics of Decision Procedures in Automated Reasoning (Cork, Ireland).]]

[24]

Downey, P. J., Sethi, R., and Tarjan, R. E. 1980. Variations on the common subexpressions problem. J. ACM 27, 4, 758--771.]]

Digital Library

[25]

Eén, N., and Sörensson, N. 2003. An extensible SAT-solver. In Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT). 502--518.]]

[26]

Filliâtre, J.-C., Owre, S., Rueß, H., and Shankar, N. 2001. ICS: Integrated canonization and solving (tool presentation). In Proceedings of the 13th International Conference on Computer Aided Verification (CAV'2001). G. Berry, H. Comon, and A. Finkel, Eds. Lecture Notes in Computer Science, vol. 2102. Springer-Verlag, New York, 246--249.]]

Digital Library

[27]

Flanagan, C., Joshi, R., Ou, X., and Saxe, J. B. 2003. Theorem proving using lazy proof explanation. In Proceedings of the 15th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 2725. Springer-Verlag, New York.]]

[28]

Ganzinger, H., Hagen, G., Nieuwenhuis, R., Oliveras, A., and Tinelli, C. 2004. DPLL(T): Fast Decision Procedures. In Proceedings of the 16th International Conference on Computer Aided Verification (CAV'04) (Boston, MA). R. Alur and D. Peled, Eds. Lecture Notes in Computer Science, vol. 3114. Springer-Verlag, New York, 175--188.]]

[29]

Goldberg, E., and Novikov, Y. 2002. BerkMin: A fast and robust SAT-solver. In Proceedings of the Symposium on Design, Automation, and Test in Europe (DATE '02). 142--149.]]

Digital Library

[30]

Hodges, W. 1993. Model Theory. Enclyclopedia of mathematics and its applications, vol. 42. Cambridge University Press, Cambridge, MA.]]

[31]

Jaffar, J., and Maher, M. 1994. Constraint Logic Programming: A Survey. J. Logic Prog. 19/20, 503--581.]]

[32]

Lahiri, S. K., and Seshia, S. A. 2004. The UCLID Decision Procedure. In Computer Aided Verification, 16th International Conference (CAV). Lecture Notes in Computer Science, vol. 3114. Springer-Verlag, New York, 475--478.]]

[33]

Manolios, P., and Srinivasan, S. K. 2005a. A computationally efficient method based on commitment refinement maps for verifying pipelined machines. In Proceedings of the ACM IEEE International Conference on Formal Methods and Models for Co-Design (MEMOCODE). ACM, New York.]]

Digital Library

[34]

Manolios, P., and Srinivasan, S. K. 2005b. Refinement maps for efficient verification of processor models. In Proceedings of the Design, Automation and Test in Europe Conference and Exposition (DATE). IEEE Computer Society, 1304--1309.]]

Digital Library

[35]

Marques-Silva, J., and Sakallah, K. A. 1999. GRASP: A search algorithm for propositional satisfiability. IEEE Trans. Comput. 48, 5 (May), 506--521.]]

Digital Library

[36]

Meir, O., and Strichman, O. 2005. Yet another decision procedure for equality logic. In Proceedings of the 17th International Conference on Computer Aided Verification (CAV'05) (Edimburgh, Scotland). K. Etessami and S. K. Rajamani, Eds. Lecture Notes in Computer Science, vol. 3576. Springer-Verlag, New York, 307--320.]]

Digital Library

[37]

Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., and Malik, S. 2001. Chaff: Engineering an efficient SAT solver. In Proceedings of the 38th Design Automation Conference (DAC'01).]]

Digital Library

[38]

Nieuwenhuis, R., and Oliveras, A. 2003. Congruence Closure with Integer Offsets. In Proceedings of the 10h International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR), M. Vardi and A. Voronkov, Eds. Lecture Notes in Artificial Intellegence, vol. 2850. Springer-Verlag, New York, 2850. 78--90.]]

[39]

Nieuwenhuis, R., and Oliveras, A. 2005a. DPLL(T) with exhaustive theory propagation and its application to difference logic. In Proceedings of the 17th International Conference on Computer Aided Verification (CAV'05) (Edimburgh, Scotland). K. Etessami and S. K. Rajamani, Eds. Lecture Notes in Computer Science, vol. 3576. Springer-Verlag, New York, 321--334.]]

Digital Library

[40]

Nieuwenhuis, R., and Oliveras, A. 2005b. Proof-producing congruence closure. In Proceedings of the 16th International Conference on Term Rewriting and Applications (RTA'05) (Nara, Japan). J. Giesl, Ed. Lecture Notes in Computer Science, vol. 3467. Springer-Verlag, New York, 453--468.]]

Digital Library

[41]

Nieuwenhuis, R., Oliveras, A., and Tinelli, C. 2005. Abstract DPLL and abstract DPLL modulo theories. In Proceedings of the 11th International Conference Logic for Programming, Artificial Intelligence and Reasoning (LPAR). F. Baader and A. Voronkov, Eds. Lecture Notes in Computer Science, vol. 3452. Springer-Verlag, New York, 36--50.]]

[42]

Pnueli, A., Rodeh, Y., Shtrichman, O., and Siegel, M. 1999. Deciding equality formulas by small domains instantiations. In Proceedings of the 11th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 1633. Springer-Verlag, New York. 455--469.]]

Digital Library

[43]

Ranise, S., and Tinelli, C. 2003. The SMT-LIB format: An initial proposal. In Proceedings of the 1st Workshop on Pragmatics of Decision Procedures in Automated Reasoning. Miami.]]

[44]

Ryan, L. 2004. Efficient algorithms for clause-learning SAT solvers. M.S. dissertation, School of Computing Science, Simon Fraser University.]]

[45]

Schrijver, A. 1987. Theory of Linear and Integer Programming. Wiley, New York.]]

Digital Library

[46]

Seshia, S., Lahiri, S., and Bryant, R. 2003. A hybrid SAT-based decision procedure for separation logic with uninterpreted functions. In Proceedings of the 40th Design Automation Conference (DAC). 425--430.]]

Digital Library

[47]

Seshia, S. A. 2005. Adaptive eager Boolean encoding for arithmetic reasoning in verification. Ph.D. dissertation, Carnegie-Mellon University, Pittsburgh, PA.]]

Digital Library

[48]

Seshia, S. A., and Bryant, R. E. 2004. Deciding quantifier-free presburger formulas using parameterized solution bounds. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004). IEEE Computer Society Press, Los Alamitos, CA, 100--109.]]

Digital Library

[49]

Strichman, O. 2002. On solving presburger and linear arithmetic with SAT. In Proceedings of the Formal Methods in Computer-Aided Design, 4th International Conference (FMCAD 2002) (Portland, OR). M. Aagaard and J. W. O'Leary, Eds. Lecture Notes in Computer Science, vol. 2517. Springer-Verlag, New York, 160--170.]]

Digital Library

[50]

Strichman, O., Seshia, S. A., and Bryant, R. E. 2002. Deciding separation formulas with SAT. In Proceedings of the 14th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol 2404. Springer-Verlag, New York. 209--222.]]

Digital Library

[51]

Stump, A., and Tan, L.-Y. 2005. The algebra of equality proofs. In Proceedings of the 16th International Conference on Term Rewriting and Applications, RTA'05 (Nara, Japan). J. Giesl, Ed. Lecture Notes in Computer Science, vol. 3467. Springer-Verlag, New York, 469--483.]]

Digital Library

[52]

Talupur, M., Sinha, N., Strichman, O., and Pnueli, A. 2004. Range allocation for separation logic. In Proceedings of the 16th International Conference on Computer Aided Verification (CAV 2004). (Boston, MA July 13--17). Lecture Notes in Computer Science, Springer-Verlag, New York, 148--161.]]

[53]

Tinelli, C. 2002. A DPLL-based calculus for ground satisfiability modulo theories. In Proceedings of the 8th European Conference on Logics in Artificial Intelligence. Lecture Notes in Artificial Intelligence, vol. 2424. Springer-Verlag, New York, 308--319.]]

Digital Library

[54]

Tinelli, C., and Ranise, S. 2005. SMT-LIB: The Satisfiability Modulo Theories Library. http://goedel.cs.uiowa.edu/smtlib/.]]

[55]

Zhang, H. 1997. SATO: An efficient propositional prover. In Proceedings of the 14th International Conference on Automated Deduction. Springer-Verlag, New York, 272--275.]]

Digital Library

[56]

Zhang, L., Madigan, C. F., Moskewicz, M. W., and Malik, S. 2001. Efficient conflict driven learning in a Boolean satisfiability solver. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'01). 279--285.]]

Digital Library

[57]

Zhang, L., and Malik, S. 2003. Validating SAT solvers using an independent resolution-based checker: Practical implementations and other applications. In Proceedings of the 2003 Design, Automation and Test in Europe Conference (DATE 2003). IEEE Computer Society Press, Los Alamitos, CA, 10880--10885.]]

Digital Library

Cited By

Dodaro C(2024)Design and implementation of modern CDCL ASP solversIntelligenza Artificiale10.3233/IA-240019(1-21)Online publication date: 25-May-2024
https://doi.org/10.3233/IA-240019
Duong HXu DNguyen TDwyer M(2024)Harnessing Neuron Stability to Improve DNN VerificationProceedings of the ACM on Software Engineering10.1145/36437651:FSE(859-881)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643765
Desoeuvres AIosif ALüders CRadulescu ORahkooy HSeiß MSturm T(2024)A Computational Approach to Polynomial Conservation LawsSIAM Journal on Applied Dynamical Systems10.1137/22M154401423:1(813-854)Online publication date: 12-Mar-2024
https://doi.org/10.1137/22M1544014
Show More Cited By

Index Terms

Solving SAT and SAT Modulo Theories: From an abstract Davis--Putnam--Logemann--Loveland procedure to DPLL(T)

Recommendations

A modular CNF-based SAT solver
SBCCI '10: Proceedings of the 23rd symposium on Integrated circuits and system design

The state-of-the-art SAT solvers, such as Chaff [11], zChaff [18], BerkMin [5], and Minisat [2] usually share the same core techniques, for instance: the watched literals structures conflict clause recording and non-chronological backtracking. ...
Approximating Quantified SMT-Solving with SAT
SSIRI-C '11: Proceedings of the 2011 Fifth International Conference on Secure Software Integration and Reliability Improvement - Companion

Satisfiability Modulo Theories (SMT) is an extension of SAT towards FOL. SMT solvers have proven highly scalable and efficient for problems based on some ground theorems. However, SMT problems involving quantifiers and combination of theorems is a long-...
Solving constraint satisfaction problems with SAT modulo theories

Due to significant advances in SAT technology in the last years, its use for solving constraint satisfaction problems has been gaining wide acceptance. Solvers for satisfiability modulo theories (SMT) generalize SAT solving by adding the ability to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 53, Issue 6

November 2006

132 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1217856

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2006

Published in JACM Volume 53, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

551
Total Citations
View Citations
3,182
Total Downloads

Downloads (Last 12 months)133
Downloads (Last 6 weeks)16

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dodaro C(2024)Design and implementation of modern CDCL ASP solversIntelligenza Artificiale10.3233/IA-240019(1-21)Online publication date: 25-May-2024
https://doi.org/10.3233/IA-240019
Duong HXu DNguyen TDwyer M(2024)Harnessing Neuron Stability to Improve DNN VerificationProceedings of the ACM on Software Engineering10.1145/36437651:FSE(859-881)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643765
Desoeuvres AIosif ALüders CRadulescu ORahkooy HSeiß MSturm T(2024)A Computational Approach to Polynomial Conservation LawsSIAM Journal on Applied Dynamical Systems10.1137/22M154401423:1(813-854)Online publication date: 12-Mar-2024
https://doi.org/10.1137/22M1544014
Nie HSu YZhao WMu J(2024)Hybrid traffic scheduling in time‐sensitive networking for the support of automotive applicationsIET Communications10.1049/cmu2.1271318:2(111-128)Online publication date: 24-Jan-2024
https://dl.acm.org/doi/10.1049/cmu2.12713
Fiorentini CFerrari M(2024)General Clauses for SAT-Based Proof Search in Intuitionistic Propositional LogicJournal of Automated Reasoning10.1007/s10817-024-09703-868:3Online publication date: 16-Jun-2024
https://dl.acm.org/doi/10.1007/s10817-024-09703-8
Ozdemir APailoor SBassa AFerles KBarrett CDillig I(2024)Split Gröbner Bases for Satisfiability Modulo Finite FieldsComputer Aided Verification10.1007/978-3-031-65627-9_1(3-25)Online publication date: 26-Jul-2024
https://doi.org/10.1007/978-3-031-65627-9_1
Liu ZYang PZhang LHuang X(2024)DeepCDCL: A CDCL-based Neural Network Verification FrameworkTheoretical Aspects of Software Engineering10.1007/978-3-031-64626-3_20(343-355)Online publication date: 29-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-64626-3_20
Tsiskaridze NBarrett CTinelli C(2024)Generalized Optimization Modulo TheoriesAutomated Reasoning10.1007/978-3-031-63498-7_27(458-479)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63498-7_27
Shi JLiu GLi CLi Y(2024)Automated-Based Rebound Attacks on ACE PermutationTopics in Cryptology – CT-RSA 202410.1007/978-3-031-58868-6_4(78-111)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58868-6_4
Wang ZZhan BLi BCai S(2024)Efficient Local Search for Nonlinear Real ArithmeticVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-50524-9_15(326-349)Online publication date: 15-Jan-2024
https://dl.acm.org/doi/10.1007/978-3-031-50524-9_15
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents