Blick ins Buch

Theory and Applications of Satisfiability Testing – SAT 2008

11th International Conference, SAT 2008, Guangzhou, China, May 12-15, 2008, Proceedings

Hans Kleine Büning, Xishun Zhao (Herausgeber)

Buch | Softcover

X, 305 Seiten

2008 | 2008
Springer Berlin (Verlag)
978-3-540-79718-0 (ISBN)

Lese- und Medienproben

Blick ins Buch (midvox)

Artikel merken

This volume contains the papers presented at the 11th International Conference on Theory and Applications of Satis?ability Testing (SAT 2008). The series of International Conferences on Theory and Applications of S- is?ability Testing (SAT) has evolved from a ?rst workshop on SAT in 1996 to an annual international conference which is a platform for researchers studying various aspects of the propositional satis?ability problem and its applications. In the past, the SAT conference venue alternated between Europe and North America. For the ?rst time, the conference venue was in Asia, more precisely at the Zhudao Guest House, near Sun Yat-Sen University in Guangzhou, P. R. China. Many hard combinatorial problems can be encoded into SAT. Therefore - provementsonheuristics onthe practicalside,as wellastheoreticalinsightsinto SAT apply to a large range of real-world problems. More speci?cally, many - portant practical veri?cation problems can be rephrased as SAT problems. This applies to veri?cation problems in hardware and software. Thus SAT is bec- ing one of the most important core technologies to verify secure and dependable systems. The topics of the conference span practical and theoretical research on SAT and its applications and include but are not limited to proof systems, proof complexity, search algorithms, heuristics, analysis of algorithms, hard instances, randomized formulae, problem encodings, industrial applications, solvers, s- pli?ers, tools, case studies, and empirical results. SAT is interpreted in a rather broad sense: besides propositional satis?ability, it includes, for example, the - main of quanti?ed Boolean formulae (QBF) and satis?ability modulo theories (SMT).

Modelling Max-CSP as Partial Max-SAT.- A Preprocessor for Max-SAT Solvers.- A Generalized Framework for Conflict Analysis.- Adaptive Restart Strategies for Conflict Driven SAT Solvers.- New Results on the Phase Transition for Random Quantified Boolean Formulas.- Designing an Efficient Hardware Implication Accelerator for SAT Solving.- Attacking Bivium Using SAT Solvers.- SAT Modulo the Theory of Linear Arithmetic: Exact, Inexact and Commercial Solvers.- Random Instances of W[2]-Complete Problems: Thresholds, Complexity, and Algorithms.- Complexity and Algorithms for Well-Structured k-SAT Instances.- A Decision-Making Procedure for Resolution-Based SAT-Solvers.- Online Estimation of SAT Solving Runtime.- A Max-SAT Inference-Based Pre-processing for Max-Clique.- SAT, UNSAT and Coloring.- Computation of Renameable Horn Backdoors.- A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors.- Improvements to Hybrid Incremental SAT Algorithms.- Searching for Autarkies to Trim Unsatisfiable Clause Sets.- Nenofex: Expanding NNF for QBF Solving.- SAT(ID): Satisfiability of Propositional Logic Extended with Inductive Definitions.- Towards More Effective Unsatisfiability-Based Maximum Satisfiability Algorithms.- A CNF Class Generalizing Exact Linear Formulas.- How Many Conflicts Does It Need to Be Unsatisfiable?.- Speeding-Up Non-clausal Local Search for Propositional Satisfiability with Clause Learning.- Local Restarts.- Regular and General Resolution: An Improved Separation.- Finding Guaranteed MUSes Fast.

Erscheint lt. Verlag	25.4.2008
Reihe/Serie	Lecture Notes in Computer Science
Reihe/Serie	Theoretical Computer Science and General Issues
Zusatzinfo	X, 305 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	498 g
Themenwelt	Informatik ► Software Entwicklung ► Qualität / Testen
Themenwelt	Mathematik / Informatik ► Informatik ► Theorie / Studium
Schlagworte	3-SAT • algorithm • Algorithm analysis and problem complexity • algorithms • Complexity • Constraint Programming • Distributed Systems • Erfüllbarkeitsproblem der Aussagenlogik • Fault Diagnosis • Hardcover, Softcover / Informatik, EDV/Informatik • HC/Informatik, EDV/Informatik • Heuristics • Local Search • Logic • MAX-SAT • Optimization • probabilistic algorithms • Proof • proof complexity • proof systems • Proof theory • propositional logic • QBF • quantified boolean formulae • random walks • Resolution • SAT algorithms • satisfiability • satisfiability testing • SAT solvers • Searching • SMT
ISBN-10	3-540-79718-1 / 3540797181
ISBN-13	978-3-540-79718-0 / 9783540797180
Zustand	Neuware