POS-10: July 10

Pragmatics of SAT

associated with SAT

Overview

The success of SAT technology in the last decade is mainly due to both the availability of numerous efficient SAT solvers and to the growing number of problems that can efficiently be solved through a translation into SAT. If the main application in the early 2000 was bounded model checking, the current applications range from formal verification (in both software and hardware) to bioinformatics. If the users of SAT solvers were mainly researchers a decade ago, SAT solvers now ship in widely used software, such as SUSE Linux operating system or the open platform Eclipse.

Designing efficient SAT solvers requires both a good theoretical knowledge about the design of SAT solvers, i.e. how are interacting all its components, and a deep practical knowledge about how to implement efficiently such components.

The SAT community organizes regularly SAT competitive events (SAT competition or SAT Races) to evaluate available SAT solvers on a wide range of problems. The winners of those events set regularly new standards in the area.

If the systems themselves are widely spread, many details on their design or in their implementation can only be found in the source code of the systems. This is also true for the encoding of some constraints. It is usually the case that system descriptions provided for the competitive events are not detailed and that the SAT conference publishes very few system descriptions since 2005 (before that, the post proceedings could contain the system description of the competition winners, e.g. Minisat for SAT03 and Chaff 2004 for SAT04).

The aim of the pragmatics of SAT workshop is to allow researchers concerned with the design of efficient SAT solvers or SAT encodings to meet and discuss about their latest results. The workshop is also the place for users of SAT technology to present their applications.

This workshop follows the spirit of Pragmatics of Decision Procedures in Automated Reasoning organized at FLoC 2006.

More information can be found here.

Programme

Tutorial: From Parallel SAT to Distributed SAT

Youssef Hamadi, Microsoft Research

This tutorial will present an overview of parallelism in SAT. It will start with a presentation of classical divide and conquer techniques, discuss their ancient origin and compare them to more recent portfolio-based algorithms. It will then present the impact of clause-sharing on their performances and discuss various strategies used to control the communication overhead. A particular technique used to control the classical diversification/intensification tradeoff will also be presented. Finally, perspectives will be given which will relate the current parallel SAT technologies to the expected evolution of computational platforms, leading to distributed SAT solving scenarios.

Program Chairs

Daniel Le Berre, CRIL-CNRS UMR 8188, France
Allen Van Gelder, University of California, Santa Cruz, United States

Program Committee:

Josep Argelich, Universitat de Lleida, Spain
Armin Biere, Johannes Kepler University, Austria
Youssef Hamadi, Microsoft Research, United Kingdom
Olivier Roussel, CRIL-CNRS UMR 8188, France
Carsten Sinz, Karlsruhe Institute of Technology, Germany
Armando Tacchella, Università di Genova, Italy