Theory and Applications of Satisfiability Testing - SAT 2009

1. Front Matter

   PDF

2. Invited Talks

   1. SAT Modulo Theories: Enhancing SAT with Special-Purpose Algorithms

      • Robert Nieuwenhuis

      Pages 1-1

   2. Symbolic Techniques in Propositional Satisfiability Solving

      • Moshe Y. Vardi

      Pages 2-3

3. Applications of SAT

   1. Efficiently Calculating Evolutionary Tree Measures Using SAT

      • María Luisa Bonet, Katherine St. John

      Pages 4-17

   2. Finding Lean Induced Cycles in Binary Hypercubes

      • Yury Chebiryak, Thomas Wahl, Daniel Kroening, Leopold Haller

      Pages 18-31

   3. Finding Efficient Circuits Using SAT-Solvers

      • Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev

      Pages 32-44

   4. Encoding Treewidth into SAT

      • Marko Samer, Helmut Veith

      Pages 45-50

4. Complexity Theory

   1. The Complexity of Reasoning for Fragments of Default Logic

      • Olaf Beyersdorff, Arne Meier, Michael Thomas, Heribert Vollmer

      Pages 51-64

   2. Does Advice Help to Prove Propositional Tautologies?

      • Olaf Beyersdorff, Sebastian Müller

      Pages 65-72

5. Structures for SAT

   1. Backdoors in the Context of Learning

      • Bistra Dilkina, Carla P. Gomes, Ashish Sabharwal

      Pages 73-79

   2. Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences

      • Daniel Johannsen, Igor Razgon, Magnus Wahlström

      Pages 80-85

   3. On Some Aspects of Mixed Horn Formulas

      • Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer

      Pages 86-100

   4. Variable Influences in Conjunctive Normal Forms

      • Patrick Traxler

      Pages 101-113

6. Resolution and SAT

   1. Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution

      • Albert Atserias, Johannes Klaus Fichte, Marc Thurley

      Pages 114-127

   2. An Exponential Lower Bound for Width-Restricted Clause Learning

      • Jan Johannsen

      Pages 128-140

   3. Improved Conflict-Clause Minimization Leads to Improved Propositional Proof Traces

      • Allen Van Gelder

      Pages 141-146

   4. Boundary Points and Resolution

      • Eugene Goldberg

      Pages 147-160

7. Translations to CNF

   1. Sequential Encodings from Max-CSP into Partial Max-SAT

      • Josep Argelich, Alba Cabiscol, Inês Lynce, Felip Manyà

      Pages 161-166

   2. Cardinality Networks and Their Applications

      • Roberto Asín, Robert Nieuwenhuis, Albert Oliveras, Enric Rodríguez-Carbonell

      Pages 167-180

   3. New Encodings of Pseudo-Boolean Constraints into CNF

      • Olivier Bailleux, Yacine Boufkhad, Olivier Roussel

      Pages 181-194

This volume contains the papers presented at SAT 2009: 12th International Conference on Theory and Applications of Satis?ability Testing, held from June 30 to July 3, 2009 in Swansea (UK). The International Conference on Theory and Applications of Satis?ability Testing (SAT) started in 1996 as a series of workshops, and, in parallel with the growthof SAT, developedinto the main eventfor SAT research. This year’sc- ference testi?ed to the strong interest in SAT, regarding theoretical research,- searchonalgorithms,investigationsintoapplications,anddevelopmentofsolvers and software systems. As a core problem of computer science, SAT is central for many research areas, and has deep interactions with many mathematical s- jects. Major impulses for the development of SAT came from concrete practical applications as well as from fundamental theoretical research. This fruitful c- laboration can be seen in virtually all papers of this volume. There were 86 submissions (completed papers within the scope of the c- ference). Each submission was reviewed by at least three, and on average 4. 0 Programme Committee members. The Committee decided to accept 45 papers, consisting of 34 regular and 11 short papers (restricted to 6 pages). A main n- elty was a “shepherding process”, where 29% of the papers were accepted only conditionally, and requirements on necessary improvements were formulated by the ProgrammeCommittee and its installment monitored by the “shepherd” for thatpaper(using possibly severalroundsoffeedback).

• Automat
• Resolution
• algorithms
• circuit based solver
• complexity
• complexity theory
• computational complexity
• constraint programming
• default logic
• distributed algorithms
• distributed systems
• exact algorithm
• heuristics
• hybrid solving technique
• algorithm analysis and problem complexity

• Computer Science Department, Swansea University, Swansea, UK

  Oliver Kullmann

Policies and ethics