Theory and Applications of Satisfiability Testing-SAT 2010

by Strichman, Ofer; Szeider, Stefan

• ISBN13: 9783642141850
• ISBN10: 3642141854
• Format: Paperback
• Copyright: 2010-10-30
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 13th International Conference on Theory and Applications of Satisfiability Testing, SAT 2010, held in Edinburgh, UK, in July 2010 as part of the Federated Logic Conference, FLoC 2010. The 21 revised full papers presented together with 14 revised short papers and 2 invited talks were carefully selected from 75 submissions. The papers cover a broad range of topics such as proof systems and proof complexity; search algorithms and heuristics; analysis of algorithms; combinatorial theory of satisfiability; random instances vs structured instances; problem encodings; industrial applications; applications to combinatorics; solvers, simplifiers and tools; and exact and parameterized algorithms.

Table of Contents

Invited Talks
The Big Deal: Applying Constraint Satisfaction Technologies Where It Makes the Difference	p. 1
Exact Algorithms and Complexity	p. 8
Regular Papers
Improving Stochastic Local Search for SAT with a New Probability Distribution	p. 10
Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas	p. 16
Proof Complexity of Propositional Default Logic	p. 30
Automated Testing and Debugging of SAT and QBF Solvers	p. 44
Rewriting (Dependency-) Quantified 2-CNF with Arbitrary Free Literals into Existential 2-HORN	p. 58
Synthesizing Shortest Linear Straight-Line Programs over GF(2) Using SAT	p. 71
sQueezeBF: An Effective Preprocessor for QBFs Based on Equivalence Reasoning	p. 85
Non Uniform Selection of Solutions for Upper Bounding the 3-SAT Threshold	p. 99
Symmetry and Satisfiability: An Update	p. 113
A Non-prenex, Non-clausal QBF Solver with Game-State Learning	p. 128
SAT Solving with Reference Points	p. 143
Integrating Dependency Schemes in Search-Based QBF Solvers	p. 158
An Exact Algorithm for the Boolean Connectivity Problem for k-CNF	p. 172
Improving Unsatisfiability-Based Algorithms for Boolean Optimization	p. 181
Encoding Techniques, Craig Interpolants and Bounded Model Checking for Incomplete Designs	p. 194
Statistical Methodology for Comparison of SAT Solvers	p. 209
On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem	p. 223
The Seventh QBF Solvers Evaluation (QBFEVAL'10)	p. 237
Complexity Results for Linear XSAT-Problems	p. 251
Bounds on Threshold of Regular Random k-SAT	p. 264
Dynamic Scoring Functions with Variable Expressions: New SLS Methods for Solving SAT	p. 278
Short Papers
Improved Local Search for Circuit Satisfiability	p. 293
A System for Solving Constraint Satisfaction Problems with SMT	p. 300
Two Techniques for Minimizing Resolution Proofs	p. 306
On Moderately Exponential Time for SAT	p. 313
Minimising Deterministic Büchi Automata Precisely Using SAT Solving	p. 326
Exploiting Circuit Representations in QBF solving	p. 333
Reconstructing Solutions after Blocked Clause Elimination	p. 340
An Empirical Study of Optimal Noise and Runtime Distributions in Local Search	p. 346
Green-Tao Numbers and SAT	p. 352
Exact MinSAT Solving	p. 363
Uniquely Satisfiable k-SAT Instances with Almost Minimal Occurrences of Each Variable	p. 369
Assignment Stack Shrinking	p. 375
Simple but Hard Mixed Horn Formulas	p. 382
Zero-One Designs Produce Small Hard SAT Instances	p. 388
Author Index	p. 399
Table of Contents provided by Ingram. All Rights Reserved.