Model-based Transformations for Quantified Boolean Formulas

by Bubeck, Uwe

• ISBN13: 9781607505457
• ISBN10: 1607505452
• Format: Paperback
• Copyright: 2010-05-15
• Publisher: Ios Pr Inc

Summary

A popular approach for solving difficult decision problems in many areas, for example planning or verification, is to encode them as propositional formulas and to apply one of the powerful SAT solvers available today. Quantified Boolean formulas (QBF) generalize propositional logic by allowing universal and existential quantifiers over propositional variables. This permits very natural encodings which are often significantly more compact than their propositional counterparts, but also more difficult to solve. The goal of this work is to support effective use of quantification by examining close relationships between formula structure and quantifier expressiveness. Useful subclasses with lower complexity are considered, in particular quantified Horn formulas and interesting generalizations thereof. From a theoretical and a practical point of view, this work presents efficient formula transformations and a pre-processing approach which allows the elimination of weak quantifiers from given QBF formulas in order to improve the performance of QBF solvers. IOS Press is an international science, technical and medical publisher of high-quality books for academics, scientists, and professionals in all fields. Some of the areas we publish in: -Biomedicine -Oncology -Artificial intelligence -Databases and information systems -Maritime engineering -Nanotechnology -Geoengineering -All aspects of physics -E-governance -E-commerce -The knowledge economy -Urban studies -Arms control -Understanding and responding to terrorism -Medical informatics -Computer Sciences