CMP SCI 691SS - Seminar: Satisfiability Solvers and Their Applications - Spring 2008

  • Instructor:
     J. Eliot B. Moss, Professor
     Office: Computer Science Building 372
     Email: moss at cs.umass.edu
     Phone: (413) 545-4206; Fax: (413) 545-1249
     Hours: by appointment (please do!)
    
  • Class schedule:
    Seminar: Mon/Fri 3:35-4:50 CMPS 142
    NOTE: Some Monday sessions may be "bumped" by faculty candidate talks, etc.

  • Description:

    Satisfiability (SAT) solvers are now widely available and have growing applications to a wide-range of computer science problems. In this seminar we will explore the state of the art in solver technology and also of applications to fields of interest, particularly computer architecture and software verification. We may also look at related problems such as Max-SAT and quantified boolean formulae. Students will offer concise presentation and critique of papers drawn from the literature. Students will also undertake projects in either extending a solver or applying one to a problem of their choosing. Grades will be based on quality of participation and on the project work. There are no particular prerequisites for this seminar beyond a basic appreciation of proof techniques and a desire to learn about these approaches to automated verification and optimization.

  • Requirements:

  • Read all papers chosen in this survey
  • Present and critique a fair share of the papers
  • Propose and carry out a project, either extending a SAT solver or using one on a suitable problem

  • Class Documents:

  • Schedule (private to class)
  • Link to SAT conferences in UMass library digital collections
    (you must be on campus or have a UMass OIT account to use this)

  • Presentation Materials (private to class members)
    • 2008年02月08日, Eliot Moss: Burch and Dill PPT
    • 2008年02月15日, Trek Palmer: Ansotegui and Manya PDF
    • 2008年02月15日, Tim Richards: Fu, et al. PDF
    • 2008年02月25日, Hala Mostafa: Two Grid papers PPT
    • 2008年02月29日, Alan Carlin: Two papers on QBF solving PPT PDF
    • 2008年03月07日, Philipp Weis: Two papers on converting circuits to SAT PDF
    • 2008年03月10日, Siddharth Srivastava: Three papers on applying SAT to planning PDF
    • 2008年03月28日, Trek Palmer: Xie and Aiken; Dennis, et al. PDF
    • 2008年04月03日, Marek Petrik: Ladanyi et al., and Chandru and Rao PDF
    • 2008年04月18日, Hala Mostafa: Dixon I PPT
    • 2008年04月28日, Alan Carlin: Dixon II PPT

  • Draft list of papers

      SAT Background / Surveys

    • Lintao Zhang and Sharad Malik, The Quest for Efficient Boolean Satisfiability Solvers, Computer Aided Verification, 2002, 17-36. BiBTeX PDF
    • Lucas Bordeaux, Youssef Hamadi, and Lintao Zhang, Propositional Satisfiability and Constraint Programming: A comparative survey, ACM Computing Surveys, 38, 4, 2006, Article 12. BiBTeX PDF
    • Allen Van Gelder, Verifying Propositional Unsatisfiability: Pitfalls to Avoid, SAT 2007, Lecture Notes in Computer Science 4501, 328-333. BiBTeX PDF

      Dixon et al.'s generalization of SAT

    • Heidi E. Dixon, Matthew L. Ginsberg, and Andrew J. Parkes, Generalizing Boolean Satisfiability I: Background and Survey of Existing Work, Journal of AI Research, 21, 193-243, 2004. BiBTeX PDF
    • Heidi E. Dixon, Matthew L. Ginsberg, Eugene M. Luks and Andrew J. Parkes, Generalizing Boolean Satisfiability II: Theory, Journal of AI Research, 22, 481-534, 2004. BiBTeX PDF
    • Heidi E. Dixon, Matthew L. Ginsberg, David K. Hofer, Eugene M. Luks, and Andrew J. Parkes, Generalizing Boolean Satisfiability III: Implementation, Journal of AI Research, 23, 441-531, 2005. BiBTeX PDF

      Efficient SAT solving: Chaff, ZChaff, etc.

    • Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik, Chaff: Engineering an Efficient SAT Solver, Design Automation Conference (DAC), 2001, 530-535. BiBTeX PDF
    • Yogesh S. Mahajan, Zhaohui Fu, and Sharad Malik, Zchaff2004: An Efficient SAT Solver, Theory and Applications of Satisfiability Testing, 7th International Conference, SAT 2004, 360-375. BiBTeX PDF
    • Nachum Dershowitz, Ziyad Hanna, and Alexander Nadel, A Clause-Based Heuristic for SAT Solvers, Theory and Applications of Satisfiability Testing, 8th International Conference, SAT 2005, Lecture Notes in Computer Science 3569, 2005, 46-60. BiBTeX PDF
    • Nachum Dershowitz, Ziyad Hanna, and Alexander Nadel, Towards a Better Understanding of the Functionality of a Conflict-Driven SAT Solver, Theory and Applications of Satisfiability Testing, 10th International Conference, SAT 2007, Lecture Notes in Computer Science 4501, 2007, 287-293. BiBTeX PDF
    • Matthew D. T. Lewis, Tobias Schubert, and Bernd Becker, Speedup Techniques Utilized in Modern SAT Solvers, SAT 2005, Lecture Notes in Computer Science 3569, 437-443. BiBTeX PDF
    • Chi-An Wu, Ting-Hao Lin, Chih-Chun Lee, and Chung-Yang Huang, QuteSAT: a robust circuit-based SAT solver for complex circuit structure, Design Automation and Test in Europe (DATE), 2007, 1313-1318. BiBTeX PDF
    • Wahid Chrabakh and Richard Wolski, GridSAT: A System for Solving Satisfiability problems Using a Computational Grid, Parallel Computing, 23, 9, 2006, 660-687. BiBTeX PDF
    • Sean L. Foreman and Alberto M. Segre, NAGSAT: A Randomized, Complete, Parallel Solver for 3-SAT, SAT 2002, Lecture Notes in Computer Science, 236-243. BiBTeX PDF
    • Lei Fang and Michael S. Hsiao, A new hybrid solution to boost SAT solver performance, Design Automation and Test in Europe (DATE), 2007, 1307-1313. BiBTeX PDF
    • Panagiotis Manolios and Yimin Zhang, Implementing Survey Propagation on Graphics Processing Units, Theory and Applications of Satisfiability Testing (SAT 2006), 311-324. BiBTeX PDF
    • Peixin Zhong, Margaret Martonosi, Pranav Ashar, and Sharad Malik, Accelerating Boolean Satisfiability with Configurable Hardware, 6th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM '98), 186-195. BiBTeX PDF
    • Ofer Strichman, Tuning SAT Checkers for Bounded Model Checking, Computer Aided Verification, 2000, 480-494. BiBTeX PDF

      Translations to SAT

    • Randal E. Bryant, Steven M. German, and Miroslav N. Velev, Processor verification using efficient reductions of the logic of uninterpreted functions to propositional logic, ACM Transactions on Computational Logic, 2, 1, 2001, 93-134. BiBTeX PDF
    • Zhaohui Fu, Yinlei Yu, and Sharad Malik, Considering Circuit Observability Don't Cares in CNF Satisfiability, 2005 Design, Automation and Test in Europe Conference and Exposition (DATE 2005), 1108-1113. BiBTeX PDF
    • Paul Jackson and Daniel Sheridan, Clause Form Conversions for Boolean Circuits, SAT 2004, Lecture Notes in Computer Science 3542, 2004, 183-198. BiBTeX PDF
    • Panagiotis Manolios and Daron Vroon, Efficient Circuit to CNF Conversion, Theory and Applications of Satisfiability Testing (SAT 2007), 4-9. BiBTeX PDF
    • Darko Marinov, Sarfraz Khurshid, Suhabe Bugrara, Lintao Zhang, and Martin C. Rinard, Optimizations for Compiling Declarative Models into Boolean Formulas, SAT 2005, Lecture Notes in Computer Science 3569, 2005, 187-202. BiBTeX PDF
    • Roberto Sebastiani and Michele Vescovi, Encoding the Satisfiability of Modal and Description Logics into SAT: The Case Study of K(m)/ALC, SAT 2006, Lecture Notes in Computer Science 4121, 2006, 130-135. BiBTeX PDF
    • Roberto Sebastiani and Michele Vescovi, Encoding the Satisfiability of Modal and Description Logics into SAT: The Case Study of K(m)/ALC (extended version), http://www.dit.unitn.it/~rseba/sat06/extended.ps. BiBTeX PDF
    • Carlos Ansótegui and Felip Manyà, Mapping Problems with Finite-Domain Variables to Problems with Boolean Variables, SAT 2004, Lecture Notes in Computer Science 3542, 1-15. BiBTeX PDF
    • Niklas Eén and Armin Biere, Effective Preprocessing in SAT Through Variable and Clause Elimination, SAT 2005, Lecture Notes in Computer Science, 3569, 61-75. BiBTeX PDF

      Applications of SAT

    • Jerry R. Burch and David L. Dill, Automatic Verification of Pipelined Microprocessor Control, Computer Aided Verification (CAV), 6th International Conference, Lecture Notes in Computer Science 818, 1994, 68-80. BiBTeX PDF (extended version)
    • Miroslav N. Velev and Randal E. Bryant, Effective Use of Boolean Satisfiability Procedures in the Formal Verification of Superscalar and VLIW Microprocessors, Design Automation Conference, 2001, 226-231. BiBTeX PDF
    • Yichen Xie and Alexander Aiken, Scalable error detection using boolean satisfiability, Principles of Programming Languages 2005, 351-363. BiBTeX PDF
    • Greg Dennis, Felix Sheng-Ho Chang, and Daniel Jackson, Modular verification of code with SAT, Proceedings of the ACM/SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2006, 109-120. BiBTeX PDF
    • Henry A. Kautz and Bart Selman, Planning as Satisfiability, European Conference on Artificial Intelligence (ECAI), 1992, 359-363. BiBTeX PDF
    • J\"org Hoffmann, Carla P. Gomes, Bart Selman, and Henry A. Kautz, SAT Encodings of State-Space Reachability Problems in Numeric Domains, International Joint Conference on AI (IJCAI), 2007, 1918-1923. BiBTeX PDF
    • Henry A. Kautz, David A. McAllester, and Bart Selman, Encoding Plans in Propositional Logic, International Conference on Principles of Knowledge Representation and Reasoning (KR), 1996, 374-384. BiBTeX PDF
    • Henry A. Kautz and Bart Selman, Pushing the Envelope: Planning, Propositional Logic and Stochastic Search, AAAI, 1996, Vol. 2, 1194-1201. BiBTeX PDF
    • David Mitchell, Eugenia Ternovska, Faraz Hach, and Rahelah Mohebali, Model Expansion as a Framework for Modelling and Solving Search Problems, Simon Fraser Univ. Computing Science TR 2006-24. BiBTeX PDF

      Quantified Boolean Formulae (QBF)

    • Horst Samulowitz and Fahiem Bacchus, Using SAT in QBF, Principles and Practice of Constraint Programming (CP), 2005, 578-592. BiBTeX PDF
    • Lintao Zhang and Sharad Malik, Towards a Symmetric Treatment of Satisfaction and Conflicts in Quantified Boolean Formula Evaluation, Constraint Programming, 2002, 200-215. BiBTeX PDF

      Integer Linear Programming

    • Laszlo Ladányi, Ted K. Ralphs, and Leslie E. Trotter Jr., Branch, Cut, and Price: Sequential and Parallel, Computation Combinatorial Optimization, Lecture Notes in Computer Science 2441, 2001, 223-260. BiBTeX PDF
    • Vijay Chandru and M. R. Rao, Integer Programming, Indian Institute of Science, Dept. of Computer Science and Automation, Bangalore, Technical Report IISc-CSA-98-04, 1998 BiBTeX PDF

  • Course slides and tutorials gathered from the Internet

    • Lintao Zhang's SAT Tutorial Slides (PDF) Part 1 Part 2 Part 3
    • Victor Marek's course notes on Mathematics of Satisfiability PDF
    • Unattributed slides on Zchaff PDF
    • Michael Trick's Integer Programming Tutorial (html)
    • Tutorial slides on the SYMPHONY Mixed Integer Linear Programming package PDF


  • BiBTeX entries for papers:
  • AltStyle によって変換されたページ (->オリジナル) /