SAT2000 : Highlights of Satisfiability Research in the Year 2000

by Gent, Ian; Gentles, Ian; Maaren, Hans Van; Walsh, Toby

• ISBN13: 9781586030612
• ISBN10: 1586030612
• Edition: 1st
• Format: Hardcover
• Copyright: 2000-08-01
• Publisher: Ios Pr Inc

Summary

The book is devoted to various disciplines in Satisfiability research and aims to give the reader an impression of the state of the art of this research in the Year 2000. It consists of a compilation of articles on this subject which have appeared, or will appear in the periodicals. The disciplines covered fall (not entirely neatly) into four categories: complete methods, stochastic methods, applications, and extensions beyond propositional SAT.

Table of Contents

Preface	p. 1
Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems	p. 15
Local Search Algorithms for SAT: An Empirical Evaluation	p. 43
Guided Local Search for Solving SAT and Weighted MAX-SAT Problems	p. 89
Non-systematic Search and No-good Learning	p. 107
SAT Local Search Algorithms: Worst-Case Study	p. 153
New Worst-Case Upper Bounds for SAT	p. 167
Relaxations of the Satisfiability Problem using Semidefinite Programming	p. 189
Resolution versus Search: Two Strategies for SAT	p. 215
The Propositional Formula Checker HeerHugo	p. 261
SATLIB: An Online Resource for Research on SAT	p. 283
Unique Solution Instance Generation for the 3-Satisfiability (3SAT) Problem	p. 293
Implementing the Davis-Putnam Method	p. 309
Proving Consistency Assertions for Automotive Product Data Management	p. 327
Logical Cryptanalysis as a SAT Problem: Encoding and Analysis of the U.S. Data Encryption Standard	p. 343
A SAT Solver Using Reconfigurable Hardware and Virtual Logic	p. 377
SAT-Based Decision Procedures for Classical Modal Logics	p. 403
Evaluating Optimised Decision Procedures for Propositional Modal K[subscript (m)] Satisfiability	p. 427
Using Resolution for Testing Modal Satisfiability and Building Models	p. 459
An Algorithm to Evaluate Quantified Boolean Formulae and its Experimental Evaluation	p. 485
Stochastic Boolean Satisfiability	p. 523
Author Index	p. 561
Table of Contents provided by Syndetics. All Rights Reserved.