Skip to main content
  • Conference proceedings
  • © 2011

Theory and Application of Satisfiability Testing

14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011, Proceedings

  • Up-to-date results
  • Fast track conference proceedings
  • State-of-the-art report

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 6695)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Conference series link(s): SAT: International Conference on Theory and Applications of Satisfiability Testing

Conference proceedings info: SAT 2011.

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (37 papers)

  1. Front Matter

  2. Technical Program

    1. Session 1: Complexity Analysis

      1. Parameterized Complexity of DPLL Search Procedures
        • Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
        Pages 5-18
      2. Satisfiability Certificates Verifiable in Subexponential Time
        • Evgeny Dantsin, Edward A. Hirsch
        Pages 19-32
      3. On Variables with Few Occurrences in Conjunctive Normal Forms
        • Oliver Kullmann, Xishun Zhao
        Pages 33-46
      4. Satisfiability of Acyclic and almost Acyclic CNF Formulas (II)
        • Sebastian Ordyniak, Daniel Paulusma, Stefan Szeider
        Pages 47-60
    2. Session 2: Binary Decision Diagrams

      1. BDDs for Pseudo-Boolean Constraints – Revisited
        • Ignasi Abío, Robert Nieuwenhuis, Albert Oliveras, Enric Rodríguez-Carbonell
        Pages 61-75
    3. Session 3: Theoretical Analysis

      1. Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
        • Nadia Creignou, Frédéric Olive, Johannes Schmidt
        Pages 120-133
      2. A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs
        • Ewald Speckenmeyer, Andreas Wotzlaw, Stefan Porschen
        Pages 134-144
    4. Session 4: Extraction of Minimal Unsatisfiable Subsets

      1. Minimally Unsatisfiable Boolean Circuits
        • Anton Belov, Joao Marques-Silva
        Pages 145-158
      2. On Improving MUS Extraction Algorithms
        • Joao Marques-Silva, Ines Lynce
        Pages 159-173
      3. Faster Extraction of High-Level Minimal Unsatisfiable Cores
        • Vadim Ryvchin, Ofer Strichman
        Pages 174-187
    5. Session 5: SAT Algorithms

      1. On Freezing and Reactivating Learnt Clauses
        • Gilles Audemard, Jean-Marie Lagniez, Bertrand Mazure, Lakhdar Saïs
        Pages 188-200
      2. Efficient CNF Simplification Based on Binary Implication Graphs
        • Marijn J. H. Heule, Matti Järvisalo, Armin Biere
        Pages 201-215
      3. Between Restarts and Backjumps
        • Antonio Ramos, Peter van der Tak, Marijn J. H. Heule
        Pages 216-229
    6. Session 6: Quantified Boolean Formulae

      1. Abstraction-Based Algorithm for 2QBF
        • Mikoláš Janota, Joao Marques-Silva
        Pages 230-244

Other Volumes

  1. Theory and Applications of Satisfiability Testing - SAT 2011

About this book

This book constitutes the refereed proceedings of the 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011, held in Ann Arbor, MI, USA in June 2011.

The 25 revised full papers presented together with abstracts of 2 invited talks and 10 poster papers were carefully reviewed and selected from 57 submissions. The papers are organized in topical sections on complexity analysis, binary decision diagrams, theoretical analysis, extraction of minimal unsatisfiable subsets, SAT algorithms, quantified Boolean formulae, model enumeration and local search, and empirical evaluation.

Editors and Affiliations

  • University of Michigan, Ann Arbor, USA

    Karem A. Sakallah

  • LRI / CNRS UMR8623 / INRIA Saclay, Univ Paris-Sud, Orsay, France

    Laurent Simon

Bibliographic Information

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access