Theory and Applications of Satisfiability Testing - SAT 2009
Springer Berlin (Verlag)
978-3-642-02776-5 (ISBN)
Invited Talks.- SAT Modulo Theories: Enhancing SAT with Special-Purpose Algorithms.- Symbolic Techniques in Propositional Satisfiability Solving.- Applications of SAT.- Efficiently Calculating Evolutionary Tree Measures Using SAT.- Finding Lean Induced Cycles in Binary Hypercubes.- Finding Efficient Circuits Using SAT-Solvers.- Encoding Treewidth into SAT.- Complexity Theory.- The Complexity of Reasoning for Fragments of Default Logic.- Does Advice Help to Prove Propositional Tautologies?.- Structures for SAT.- Backdoors in the Context of Learning.- Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences.- On Some Aspects of Mixed Horn Formulas.- Variable Influences in Conjunctive Normal Forms.- Resolution and SAT.- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution.- An Exponential Lower Bound for Width-Restricted Clause Learning.- Improved Conflict-Clause Minimization Leads to Improved Propositional Proof Traces.- Boundary Points and Resolution.- Translations to CNF.- Sequential Encodings from Max-CSP into Partial Max-SAT.- Cardinality Networks and Their Applications.- New Encodings of Pseudo-Boolean Constraints into CNF.- Efficient Term-ITE Conversion for Satisfiability Modulo Theories.- Techniques for Conflict-Driven SAT Solvers.- On-the-Fly Clause Improvement.- Dynamic Symmetry Breaking by Simulating Zykov Contraction.- Minimizing Learned Clauses.- Extending SAT Solvers to Cryptographic Problems.- Solving SAT by Local Search.- Improving Variable Selection Process in Stochastic Local Search for Propositional Satisfiability.- A Theoretical Analysis of Search in GSAT.- The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT.- Hybrid SAT Solvers.- A Novel Approach to Combine a SLS- and a DPLL-Solverfor the Satisfiability Problem.- Building a Hybrid SAT Solver via Conflict-Driven, Look-Ahead and XOR Reasoning Techniques.- Automatic Adaption of SAT Solvers.- Restart Strategy Selection Using Machine Learning Techniques.- Instance-Based Selection of Policies for SAT Solvers.- Width-Based Restart Policies for Clause-Learning Satisfiability Solvers.- Problem-Sensitive Restart Heuristics for the DPLL Procedure.- Stochastic Approaches to SAT Solving.- (1,2)-QSAT: A Good Candidate for Understanding Phase Transitions Mechanisms.- VARSAT: Integrating Novel Probabilistic Inference Techniques with DPLL Search.- QBFs and Their Representations.- Resolution and Expressiveness of Subclasses of Quantified Boolean Formulas and Circuits.- A Compact Representation for Syntactic Dependencies in QBFs.- Beyond CNF: A Circuit-Based QBF Solver.- Optimisation Algorithms.- Solving (Weighted) Partial MaxSAT through Satisfiability Testing.- Nonlinear Pseudo-Boolean Optimization: Relaxation or Propagation?.- Relaxed DPLL Search for MaxSAT.- Branch and Bound for Boolean Optimization and the Generation of Optimality Certificates.- Exploiting Cycle Structures in Max-SAT.- Generalizing Core-Guided Max-SAT.- Algorithms for Weighted Boolean Optimization.- Distributed and Parallel Solving.- PaQuBE: Distributed QBF Solving with Advanced Knowledge Sharing.- c-sat: A Parallel SAT Solver for Clusters.
| Erscheint lt. Verlag | 19.6.2009 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
| Zusatzinfo | XII, 540 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 830 g |
| Themenwelt | Informatik ► Software Entwicklung ► Qualität / Testen |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| Schlagworte | Algorithm analysis and problem complexity • algorithms • Automat • circuit based solver • Complexity • Complexity theory • Computational Complexity • Constraint Programming • Default Logic • distributed algorithms • Distributed Systems • exact algorithm • Hardcover, Softcover / Informatik, EDV/Informatik • Heuristics • hybrid solving technique • Local Search • master/slave architecture • MAX-SAT • Message Passing • Nonmonotonic Reasoning • Optimization • polynomial time reduction • probabilistic inference • proof complexity • proof systems • propositional logic • pseudo-boolean • QBF • quantified boolean formulae • random walks • Resolution • SAT algorithms • satisfiability • satisfiability testing • SAT solvers • SAT translation • Searching |
| ISBN-10 | 3-642-02776-8 / 3642027768 |
| ISBN-13 | 978-3-642-02776-5 / 9783642027765 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
