SCAN

Abstracts of Publications about SCAN

1. Quantifier Elimination in Second-Order Predicate Logic

An algorithm is presented which eliminates second-order quantifiers over predicate variables in formulae of type $\exists P_1 ,..., P_n\ F$ where $F$ is an arbitrary formula of first--order predicate logic. The resulting formula is equivalent to the original formula - if the algorithm terminates. The algorithm can for example be applied to do interpolation, to eliminate the second--order quantifiers in circumscription, to compute the correlations between structures and power structures, to compute semantic properties corresponding to Hilbert axioms in non classical logics and to compute model theoretic semantics for new logics.

2. Towards Automating Duality

Dualities between different theories occur frequently inmathematics and logic --- between syntax and semantics of a logic, between structures and power structures, between relations and relational algebras, to name just a few. In this paper we show for the case of structures and power structures how corresponding properties of the two related structures can be computed fully automatically by means of quantifier elimination algorithms and predicate logic theorem provers. We illustrate the method with a large number of examples and we give enough technical hints to enable the reader who has access to the {\sc Otter} theorem prover to experiment herself.

3. SCAN and Systems of Conditional Logic

The SCAN algorithm has been proposed for second order quantifier elimination. In particular it can be applied to find correspondence axioms for systems of modal logic. Up to now, what has been studied are systems with unary modal operators. 17 In this paper we study how SCAN can be applied to various systems of conditional logic, which are logical systems with binary modal operators.

4. SCAN-Elimination of Predicate Quantifiers

5. Quantifier Elimination in Second-Order Predicate Logic

6. Quantifier Elimination Technics for Program Validation

7. SCAN is complete for all Sahlqvist formulae

SCAN is an algorithm for reducing monadic existential second-order logic formulae to equivalent simpler formulae, often first-order logic formulae. It is provably impossible for such a reduction to first-order logic to be always successful, even if there is an equivalent first-order formula for a second-order logic formula. In this paper we show that SCAN successfully computes the first-order equivalents of all Sahlqvist formulae in the classical (multi-)modal language.

8. Second-Order Quantifier Elimination: Foundations, Computational Aspects and Applications

In recent years there has been an increasing use of logical methods and significant new developments have been spawned in several areas of computer science, ranging from artificial intelligence and software engineering to agent-based systems and the semantic web. In the investigation and application of logical methods there is a tension between: the need for a representational language strong enough to express domain knowledge of a particular application, and the need for a logical formalism general enough to unify several reasoning facilities relevant to the application, on the one hand, and the need to enable computationally feasible reasoning facilities, on the other hand.

Second-order logics are very expressive and allow us to represent domain knowledge with ease, but there is a high price to pay for the expressiveness. Most second-order logics are incomplete and highly undecidable. It is the quantifiers which bind relation symbols that make second-order logics computationally unfriendly. It is therefore desirable to eliminate these second-order quantifiers, when this is mathematically possible; and often it is. If second-order quantifiers are eliminable we want to know under which conditions, we want to understand the principles and we want to develop methods for second-order quantifier elimination.
This book provides the first comprehensive, systematic and uniform account of the state-of-the-art of second-order quantifier elimination in classical and non-classical logics. It covers the foundations, it discusses in detail existing second-order quantifier elimination methods, and it presents numerous examples of applications and non-standard uses in different areas. These include:

• classical and non-classical logics,
• correspondence and duality theory,
• knowledge representation and description logics,
• commonsense reasoning and approximate reasoning,
• relational and deductive databases, and
• complexity theory.