 SecondOrder Quantifier Elimination
Foundations, Computational Aspects and Applications
Dov M. Gabbay, Renate A. Schmidt and Andrzej Szalas
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 agentbased 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.
Secondorder 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 secondorder logics are incomplete and highly undecidable. It is the quantifiers which bind relation symbols that make secondorder logics computationally unfriendly. It is therefore desirable to eliminate these secondorder quantifiers, when this is mathematically possible; and often it is.
If secondorder quantifiers are eliminable we want to know under which conditions, we want to understand the principles and we want to develop methods for secondorder quantifier elimination.
This book provides the first comprehensive, systematic and uniform account of the stateoftheart of secondorder quantifier elimination in classical and nonclassical logics. It covers the foundations, it discusses in detail existing secondorder quantifier elimination methods, and it presents numerous examples of applications and nonstandard uses in different areas.
These include:
classical and nonclassical logics,
correspondence and duality theory,
knowledge representation and description logics,
commonsense reasoning and approximate reasoning,
relational and deductive databases, and
complexity theory.
The book is intended for anyone interested in the theory and application of logics in computer science and artificial intelligence.
April 2008
ISBN 9781904987567
Buy from Amazon: UK US
