Theory and Applications of Satisfiability Testing - SAT 2007

1. Front Matter

   PDF

2. SAT: Past and Future

   • Martin Davis

   Pages 1-2

3. Encodings of Problems in Effectively Propositional Logic

   • Juan Antonio Navarro-Pérez, Andrei Voronkov

   Pages 3-3

4. Efficient Circuit to CNF Conversion

   • Panagiotis Manolios, Daron Vroon

   Pages 4-9

5. Mapping CSP into Many-Valued SAT

   • Carlos Ansótegui, María Luisa Bonet, Jordi Levy, Felip Manyà

   Pages 10-15

6. Circuit Based Encoding of CNF Formula

   • Gilles Audemard, Lakhdar Saïs

   Pages 16-21

7. Breaking Symmetries in SAT Matrix Models

   • Inês Lynce, Joao Marques-Silva

   Pages 22-27

8. Partial Max-SAT Solvers with Clause Learning

   • Josep Argelich, Felip Manyà

   Pages 28-40

9. MiniMaxSat: A New Weighted Max-SAT Solver

   • Federico Heras, Javier Larrosa, Albert Oliveras

   Pages 41-55

10. Solving Multi-objective Pseudo-Boolean Problems

    • Martin Lukasiewycz, Michael Glaß, Christian Haubelt, Jürgen Teich

    Pages 56-69

11. Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities

    • Arist Kojevnikov

    Pages 70-79

12. Horn Upper Bounds and Renaming

    • Marina Langlois, Robert H. Sloan, György Turán

    Pages 80-93

13. Matched Formulas and Backdoor Sets

    • Stefan Szeider

    Pages 94-99

14. Short XORs for Model Counting: From Theory to Practice

    • Carla P. Gomes, Joerg Hoffmann, Ashish Sabharwal, Bart Selman

    Pages 100-106

15. Variable Dependency in Local Search: Prevention Is Better Than Cure

    • Steven Prestwich

    Pages 107-120

16. Combining Adaptive Noise and Look-Ahead in Local Search for SAT

    • Chu Min Li, Wanxia Wei, Harry Zhang

    Pages 121-133

17. From Idempotent Generalized Boolean Assignments to Multi-bit Search

    • Marijn Heule, Hans van Maaren

    Pages 134-147

18. Satisfiability with Exponential Families

    • Dominik Scheder, Philipp Zumstein

    Pages 148-158

19. Formalizing Dangerous SAT Encodings

    • Alexander Hertel, Philipp Hertel, Alasdair Urquhart

    Pages 159-172

20. Algorithms for Variable-Weighted 2-SAT and Dual Problems

    • Stefan Porschen, Ewald Speckenmeyer

    Pages 173-186

This volume contains the papers presented at SAT 2007: 10th International Conference on Theory and Applications of Satis?ability Testing. The International Conferences on Theory and Applications of Satis?ability Testing (SAT) originated in 1996 as a series of workshops “on Satis?ability.” By the third meeting in 2000, the workshop had attracted a mix of theorists and experimentalists whose common interest was the enhancement of our basic understanding of the theoretical underpinnings of the Satis?ability problem as well as the development of scalable algorithms for its solution in a wide range of application domains. In 2002 a competition of SAT solvers was inaugurated to spur further algorithmic and implementation developments, and to create an eclectic collection of benchmarks. The competition—expanded in subsequent years to include pseudo Boolean, QBF, and MAX-SAT solvers—has become an integralpartofthesemeetings,addinganelementofexcitementandanticipation. Theinterplaybetweentheoryandapplication,aswellastheincreasedinterestin Satis?abilityfromawider communityofresearchers,ledtothe naturalevolution of these initial workshops into the current conference format. The annual SAT conference is now universally recognized as “the venue” for publishing the latest advances in SAT research.

• Counting
• MAX-SAT
• algorithms
• constraint programing
• distributed systems
• fault diagnosis
• heuristics
• learning
• local search
• logic
• optimization
• probabilistic algorithms
• proof
• proof complexity
• robot
• algorithm analysis and problem complexity

Policies and ethics