Marc Herbstritt

Satisfiability: from Core Algorithms to Novel Application Domains Marc Herbstritt

The verification of systems to guarantee theircorrect behavior is discussed in this book. Themainly applied algorithmic method is the modelchecking technique combined with algorithmsfor solving the satisfiability problem (short: SAT). SAT-based verification of discrete systems has becomeone of the most effective technique within the last10 years, such that industrial as well as academicapplications heavily rely on it. The book covers the whole range of a SAT-based toolapplication. We propose extensions and concepts thatconcentrate on the core of a SAT-solver. However, these proposals are then transferred to novelverification models. Moreover, we describe approaches that incorporate the structure ofthe problem to exploit knowledge gained during theverification process on the level of the SAT-solver. The main focus of the book is on the verification ofincomplete system designs, which occur for example inthe early phase of a design. We describe variousSAT-based modeling concepts that vary regarding theirexpressiveness and computational resources. Theproposed methods are evaluated experimentally toguarantee their applicability in practice.