Skip to main content
SpringerLink
Log in
Book cover

Theory and Application of Satisfiability Testing

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

  • Conference proceedings
  • © 2011

Overview

Editors:
  1. Karem A. Sakallah

    1. University of Michigan, Ann Arbor, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Laurent Simon

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • 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)

Included in the following conference series:

Conference proceedings info: SAT 2011.

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

Access this book

Log in via an institution
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

Licence this eBook for your library

Institutional subscriptions

Table of contents (37 papers)

  1. Front Matter

    Download chapter PDF

  3. 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
      2. DPLL+ROBDD Derivation Applied to Inversion of Some Cryptographic Functions
        • Alexey Ignatiev, Alexander Semenov
        Pages 76-89
      3. <i>Ï€</i>DD: A New Decision Diagram for Efficient Problem Solving in Permutation Space
        • Shin-ichi Minato
        Pages 90-104

    3. Session 3: Theoretical Analysis

      1. How to Apply SAT-Solving for the Equivalence Test of Monotone Normal Forms
        • Martin Mundhenk, Robert Zeranski
        Pages 105-119
      2. Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
        • Nadia Creignou, Frédéric Olive, Johannes Schmidt
        Pages 120-133
      3. 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
Back to top

Other volumes

  1. Theory and Applications of Satisfiability Testing - SAT 2011

Keywords

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

Publish with us

Policies and ethics

Back to top

Search

Navigation