University Homepage School Homepage School Contacts School Search

Michael Fourman

Last modified: Mon Mar 24 17:34:48 GMT 2003

Theory

NP-Completeness and Cook's Theorem, Anthony Galton, Logic and Computation Course Note, University of Exeter

Graph-based Algorithms for Boolean Function Manipulation, Randal E. Bryant, updated version, IEEE Transactions on Computers, C-35-8, 1986, pp. 677-91

Determining computational complexity from characteristic phase transitions, Remi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman & Lidror Troyanskyk, NATURE, VOL 400, 8 JULY 1999, pp.133-7

Analytic and Algorithmic Solution of Random Satisfiability Problems, M\'ezard,Parisi, Zecchina, Science 297, 2002, pp. 812-5;published online 27 June 2002 (10.1126/science.1073287).

Satisfied with Physics, Gomes, Selman, Science 297, 2002, pp. 784-5

The random K-satisfiability problem: from an analytic solution to an efficient algorithm. Mezard and Zecchina

On the survey-propagation equations for the random K-satisfiability problem. Parisi

Erik Mueller, Event Calculus Reasoning through Satisfiability. Journal of Logic and Computation 2004 14(5):703-730

BDD/SAT Implementation and Evaluation

Survey propagation: an algorithm for satisfiability. Braunstein Mezard, Zecchina

Design of Experiments and Evaluation of BDD Ordering Heuristics, Harlow & Brglez, Int J STTT (2001)

Faster SAT and Smaller BDDs via Commmon Function Structure, Aloul, Markov, Sakallah, University of Michigan Technical Report, December 2001

The quest for Efficient Boolean Satisfiability Solvers, Foils, Malik, CAV-CADE 2002

The quest for Efficient Boolean Satisfiability Solvers, Zhang & Malik, CADE-CAV 2002

Chaff: Engineering an Efficient SAT Solver, Moskewicz, Madigan, Zhao, Zhang, Malik, DAC 2001

Tutorials

Sebastiani CADE 04

Tools and Documentation

libbdd (3)