SAT: references on satisfiability

collected by Ian P. Gent
ipg@cs.strath.ac.uk
Toby Walsh
tw@cs.strath.ac.uk

Applications

Quasigroup existence

Automated reasoning and exhaustive search: quasigroup existence problems. .
Slaney, J., M. Fujita, and M. Stickel. Computers and Mathematics with Applications 29 (1995), 115-132.

Specifying Latin Square Problems in Propositional Logics . Hantao Zhang.

Solving Open Quasigroup Problems by Propositional Reasoning . Hantao Zhang and Jieh Hsiang.

Planning

Planning as Satisfiability
Henry Kautz and Bart Selman, Proceedings ECAI-92.

Encoding Plans in Propositional Logic
Henry Kautz, David McAllester, and Bart Selman, Proc. KR-96.

Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search
Henry Kautz and Bart Selman, Proc. AAAI-96.

BLACKBOX: A New Approach to the Application of Theorem Proving to Problem Solving
Henry Kautz and Bart Selman. Working notes of the Workshop on Planning as Combinatorial Search, held in conjunction with AIPS-98, Pittsburgh, PA, 1998.

The Role of Domain-Specific Knowledge in the Planning as Satisfiability Framework
Henry Kautz and Bart Selman. Proc. AIPS-98, Pittsburgh, PA, 1998.

Steiner trees

Solving Problems with Hard and Soft Constraints Using A Stochastic Algorithm for MAX-SAT"
Yueyun Jiang, Henry Kautz, and Bart Selman, 1st International Joint Workshop on Artificial Intelligence and Operations Research, 1995.

General Stochastic Approach to Solving Problems with Hard and Soft Constraints"
Henry Kautz, Bart Selman, and Yueyen Jiang. In The Satisfiability Problem: Theory and Applications, Dingzhu Gu, Jun Du, and Panos Pardalos (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 35, American Mathematical Society, 1997, pages 573-586.

Hardware

Timing Analysis Using Propositional Satisfiability, Luís Guerra e Silva, João P. Marques-Silva, Luís M. Silveira and Karem A. Sakallah, in Proceedings of the IEEE International Conference on Electronics, Circuits and Systems (ICECS), September 1998.

Realistic Delay Modeling in Satisfiability-Based Timing Analysis, Luís Guerra e Silva, João P. Marques-Silva, Luís M. Silveira and Karem A. Sakallah, in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), May 1998.

Robust Search Algorithms for Test Pattern Generation, João P. Marques-Silva and Karem A. Sakallah, in Proceedings of the IEEE Fault-Tolerant Computing Symposium, June 1997.

Search Algorithms for Satisfiability Problems in Combinational Switching Circuits , João P. Marques-Silva, Ph.D. Dissertation, EECS Department, University of Michigan, May 1995.