Theory and Applications of Satisfiability Testing

The 7th International Conference on Theory and Applications of Satis?ab- ity Testing (SAT 2004) was held 10 13 May 2004 in Vancouver, BC, Canada. The conference featured 9 technical paper sessions, 2 poster sessions, as well as the 2004 SAT Solver Competition and the 2004 QBF Solver Evaluation. It also included invited talks by Stephen A. Cook (University of Toronto) and Kenneth McMillan (Cadence Berkeley Labs). The 89 participants represented no less than 17 countries and four continents. SAT 2004 continued the series of meetings which started with the Workshops on Satis?ability held in Siena, Italy (1996), Paderborn, Germany (1998) and Renesse, The Netherlands (2000); the Workshop on Theory and Applications of Satis?ability Testing held in Boston, USA(2001);theSymposiumonTheoryandApplicationsofSatis?abilityTesting held in Cincinnati, USA (2002); and the 6th International Conference on Theory and Applications of Satis?ability Testing held in Santa Margherita Ligure, Italy (2003). The International Conference on Theory and Applications of Satis?ability Testing is the primary annual meeting for researchers studying the propo- tional satis?ability problem (SAT), a prominent problem in both theoretical and applied computer science. SAT lies at the heart of the most important open problem in complexity theory (P vsNP) and underlies many applications in, among other examples, arti?cial intelligence, operations research and electronic design engineering. The primary objective of the conferences is to bring together researchersfromvariousareasandcommunities,includingtheoreticalandexp- imental computer science as well as many relevant application areas, to promote collaboration and the communication of new theoretical and practical results in SAT-related research and its industrial applications.

Klappentext

research and its industrial applications.

Inhalt
Mapping Problems with Finite-Domain Variables to Problems with Boolean Variables.- Mapping Problems with Finite-Domain Variables to Problems with Boolean Variables.- A SAT-Based Decision Procedure for the Boolean Combination of Difference Constraints.- An Algebraic Approach to the Complexity of Generalized Conjunctive Queries.- Incremental Compilation-to-SAT Procedures.- Resolve and Expand.- Looking Algebraically at Tractable Quantified Boolean Formulas.- Derandomization of Schuler's Algorithm for SAT.- Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank.- QBF Reasoning on Real-World Instances.- Automatic Extraction of Functional Dependencies.- Algorithms for Satisfiability Using Independent Sets of Variables.- Aligning CNF- and Equivalence-Reasoning.- Using DPLL for Efficient OBDD Construction.- Approximation Algorithm for Random MAX-kSAT.- Clause Form Conversions for Boolean Circuits.- From Spin Glasses to Hard Satisfiable Formulas.- CirCUs: A Hybrid Satisfiability Solver.- Equivalence Models for Quantified Boolean Formulas.- Search vs. Symbolic Techniques in Satisfiability Solving.- Worst Case Bounds for Some NP-Complete Modified Horn-SAT Problems.- Satisfiability Threshold of the Skewed Random k-SAT.- NiVER: Non-increasing Variable Elimination Resolution for Preprocessing SAT Instances.- Analysis of Search Based Algorithms for Satisfiability of Propositional and Quantified Boolean Formulas Arising from Circuit State Space Diameter Problems.- UBCSAT: An Implementation and Experimentation Environment for SLS Algorithms for SAT and MAX-SAT.- SAT Solver Competition and QBF Solver Evaluation (Invited Papers).- Fifty-Five Solvers in Vancouver: The SAT 2004 Competition.- March_eq: Implementing Additional Reasoning into an Efficient Look-Ahead SATSolver.- Zchaff2004: An Efficient SAT Solver.- The Second QBF Solvers Comparative Evaluation.