Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
2008 Technical Reports

Propositional Satisfiability: Algorithms and Applications

Anton Belov

Technical Report CSE-2008-06

York University

September 5, 2008


In the first part of this paper we survey a number of algorithms for solving the propositional satisfiability problem (SAT). We dedicate a large amount of attention to the non-clausal SAT algorithms, that is, the algorithms that work on arbitrary propositional formulas, and to the circuit SAT algorithms that work on Boolean circuit representation of formulas. We also discuss some of the non-mainstream clausal SAT algorithms.The second part of this paper discusses some of the practical applications ofSAT, particularly to Bounded Model Checking and to Satisfiability Modulo Theories.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.