Skip to main content
  • Conference proceedings
  • © 2005

Theory and Applications of Satisfiability Testing

7th International Conference, SAT 2004, Vancouver, BC, Canada, May 10-13, 2004, Revised Selected Papers

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

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 2004.

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 (28 papers)

  1. Front Matter

  2. Mapping Problems with Finite-Domain Variables to Problems with Boolean Variables

    1. A SAT-Based Decision Procedure for the Boolean Combination of Difference Constraints

      • Alessandro Armando, Claudio Castellini, Enrico Giunchiglia, Marco Maratea
      Pages 16-29
    2. An Algebraic Approach to the Complexity of Generalized Conjunctive Queries

      • Michael Bauland, Philippe Chapdelaine, Nadia Creignou, Miki Hermann, Heribert Vollmer
      Pages 30-45
    3. Incremental Compilation-to-SAT Procedures

      • Marco Benedetti, Sara Bernardini
      Pages 46-58
    4. Resolve and Expand

      • Armin Biere
      Pages 59-70
    5. Derandomization of Schuler’s Algorithm for SAT

      • Evgeny Dantsin, Alexander Wolpert
      Pages 80-88
    6. QBF Reasoning on Real-World Instances

      • Enrico Giunchiglia, Massimo Narizzano, Armando Tacchella
      Pages 105-121
    7. Automatic Extraction of Functional Dependencies

      • Éric Grégoire, Richard Ostrowski, Bertrand Mazure, Lakhdar Saïs
      Pages 122-132
    8. Algorithms for Satisfiability Using Independent Sets of Variables

      • Ravi Gummadi, N. S. Narayanaswamy, R. Venkatakrishnan
      Pages 133-144
    9. Aligning CNF- and Equivalence-Reasoning

      • Marijn Heule, Hans van Maaren
      Pages 145-156
    10. Using DPLL for Efficient OBDD Construction

      • Jinbo Huang, Adnan Darwiche
      Pages 157-172
    11. Approximation Algorithm for Random MAX-kSAT

      • Yannet Interian
      Pages 173-182
    12. Clause Form Conversions for Boolean Circuits

      • Paul Jackson, Daniel Sheridan
      Pages 183-198
    13. From Spin Glasses to Hard Satisfiable Formulas

      • Haixia Jia, Cris Moore, Bart Selman
      Pages 199-210
    14. CirCUs: A Hybrid Satisfiability Solver

      • HoonSang Jin, Fabio Somenzi
      Pages 211-223
    15. Equivalence Models for Quantified Boolean Formulas

      • Hans Kleine Büning, Xishun Zhao
      Pages 224-234
    16. Search vs. Symbolic Techniques in Satisfiability Solving

      • Guoqiang Pan, Moshe Y. Vardi
      Pages 235-250

Other Volumes

  1. Theory and Applications of Satisfiability Testing

Editors and Affiliations

  • Department of Computer Science, University of British Columbia Vancouver, Canada

    Holger H. Hoos

  • Computational Logic Laboratory, Simon Fraser University, Burnaby, Canada

    David G. Mitchell

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