[DL] Book Announcement: Second-Order Quantifier Elimination

[Renate Schmidt]

	  SECOND-ORDER QUANTIFIER ELIMINATION
  Foundations, Computational Aspects and Applications

			   by 
  Dov M. Gabbay, Renate A. Schmidt, and Andrzej Szalas

Studies in Logic: Mathematical Logic and Foundations, Vol. 12 
	  College Publications 2008, 308 pages 
		 ISBN 978-1-904987-56-7

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:

  o 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
  o 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:

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

The book is intended for anyone interested in the theory and
application of logics in computer science and artificial
intelligence.

Further information can be found at
http://www.cs.man.ac.uk/~schmidt/publications/GabbaySchmidtSzalas08.html