Skip to main content
SpringerLink
Log in

Theory and Applications of Satisfiability Testing

8th International Conference, SAT 2005, St Andrews, Scotland, June 19-23, 2005, Proceedings

  • Conference proceedings
  • © 2005

Overview

Editors:
  1. Fahiem Bacchus

    1. Department of Computer Science, University of Toronto, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Toby Walsh

    1. Dept. of Computer Science, Trinity College, Dublin 2

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

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

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

Included in the following conference series:

Conference proceedings info: SAT 2005.

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

  1. Front Matter

    Download chapter PDF

  2. Preface

    1. Solving Over-Constrained Problems with SAT Technology

      • Josep Argelich, Felip Manyà
      Pages 1-15

    2. A Symbolic Search Based Approach for Quantified Boolean Formulas

      • Gilles Audemard, Lakhdar Saïs
      Pages 16-30

    3. Substitutional Definition of Satisfiability in Classical Propositional Logic

      • Anton Belov, Zbigniew Stachniak
      Pages 31-45

    4. A Clause-Based Heuristic for SAT Solvers

      • Nachum Dershowitz, Ziyad Hanna, Alexander Nadel
      Pages 46-60

    5. Effective Preprocessing in SAT Through Variable and Clause Elimination

      • Niklas Eén, Armin Biere
      Pages 61-75

    6. Resolution and Pebbling Games

      • Nicola Galesi, Neil Thapen
      Pages 76-90

    7. Local and Global Complete Solution Learning Methods for QBF

      • Ian P. Gent, Andrew G. D. Rowley
      Pages 91-106

    8. Equivalence Checking of Circuits with Parameterized Specifications

      • Eugene Goldberg
      Pages 107-121

    9. Observed Lower Bounds for Random 3-SAT Phase Transition Density Using Linear Programming

      • Marijn Heule, Hans van Maaren
      Pages 122-134

    10. Simulating Cutting Plane Proofs with Restricted Degree of Falsity by Resolution

      • Edward A. Hirsch, Sergey I. Nikolenko
      Pages 135-142

    11. Resolution Tunnels for Improved SAT Solver Performance

      • Michal Kouril, John Franco
      Pages 143-157

    12. Diversification and Determinism in Local Search for Satisfiability

      • Chu Min Li, Wen Qi Huang
      Pages 158-172

    13. On Finding All Minimally Unsatisfiable Subformulas

      • Mark H. Liffiton, Karem A. Sakallah
      Pages 173-186

    14. Optimizations for Compiling Declarative Models into Boolean Formulas

      • Darko Marinov, Sarfraz Khurshid, Suhabe Bugrara, Lintao Zhang, Martin Rinard
      Pages 187-202

    15. Random Walk with Continuously Smoothed Variable Weights

      • Steven Prestwich
      Pages 203-215

    16. Derandomization of PPSZ for Unique-k-SAT

      • Daniel Rolf
      Pages 216-225

    17. Heuristics for Fast Exact Model Counting

      • Tian Sang, Paul Beame, Henry Kautz
      Pages 226-240

    18. A Scalable Method for Solving Satisfiability of Integer Linear Arithmetic Logic

      • Hossein M. Sheini, Karem A. Sakallah
      Pages 241-256

    19. DPvis – A Tool to Visualize the Structure of SAT Instances

      • Carsten Sinz, Edda-Maria Dieringer
      Pages 257-268
Back to top

Other volumes

  1. Theory and Applications of Satisfiability Testing

Keywords

About this book

The 8th International Conference on Theory and Applications of Satis?ability Testing(SAT2005)providedaninternationalforumforthemostrecentresearch on the satis?ablity problem (SAT). SAT is the classic problem of determining whether or not a propositional formula has a satisfying truth assignment. It was the ?rst problem shown by Cook to be NP-complete. Despite its seemingly specialized nature, satis?ability testing has proved to extremely useful in a wide range of di?erent disciplines, both from a practical as well as from a theoretical point of view. For example, work on SAT continues to provide insight into various fundamental problems in computation, and SAT solving technology has advanced to the point where it has become the most e?ective way of solving a number of practical problems. The SAT series of conferences are multidisciplinary conferences intended to bring together researchers from various disciplines who are interested in SAT. Topics of interest include, but are not limited to: proof systems and proof c- plexity; search algorithms and heuristics; analysis of algorithms; theories beyond the propositional; hard instances and random formulae; problem encodings; - dustrial applications; solvers and other tools. This volume contains the papers accepted for presentation at SAT 2005. The conference attracted a record number of 73 submissions. Of these, 26 papers were accepted for presentation in the technical programme. In addition, 16 - pers were accepted as shorter papers and were presented as posters during the technicalprogramme.Theacceptedpapersandposterpaperscoverthefullrange of topics listed in the call for papers.

Editors and Affiliations

  • Department of Computer Science, University of Toronto, Canada

    Fahiem Bacchus

  • Dept. of Computer Science, Trinity College, Dublin 2

    Toby Walsh

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation