SCAN
Literature
Abstracts of Publications about SCAN
In chronological order.
by Dov M. Gabbay and Hans Jürgen Ohlbach,
published in Proc. of KR 92 and in the
South African Computer Journal, 1992.
DVI,
PostScript,
BibTeXEntry
An algorithm is presented which eliminates secondorder quantifiers over predicate variables in formulae of type
$\exists P_1 ,..., P_n\ F$ where $F$ is an arbitrary formula of
firstorder 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 secondorder 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.
by Chris Brink and Dov M. Gabbay and Hans Jürgen Ohlbach,
forthcoming in a special issue.
A longer version is available as Technical Report MPII93220,
MaxPlanckInstitut für Informatik, Saarbrücken,
Germany, 1993.
DVI,
PostScript,
BibTeXEntry
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.
by Andreas Herzig,
Technical Report MPII962007,
MaxPlanckInstitut für Informatik,
Saarbrücken, September 1996.
PostScript,
BibTeXEntry
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.
by Hans Jürgen Ohlbach.
In McRobbie, M. A. and Slaney, J. K. (eds.),
Automated Deduction: CADE13.
Lecture Notes in Artificial Intelligence 1104, Springer, 161165, 1996.
HDVI,
PostScript,
BibTeXEntry
by Thorsten Engel.
Diplomarbeit, Fachbereich Informatik, Univ. des Saarlandes,
Saarbrücken, October 1996.
HDVI,
PostScript,
BibTeXEntry
by J.P. Bodeveix and M. Filali.
Technical Report IRIT9744R, Institut de Recherche en Informatique de
Toulouse, October 1997.
PostScript
by V. Goranko, U. Hustadt, R. A. Schmidt and D. Vakarelov
published in Proceedings of
Relational and KleeneAlgebraic Methods in Computer Science (RelMiCS 7).
Lecture Notes in Computer Science
3051,
Springer,
149162
(2004).
BiBTeX,
PDF.
SCAN is an algorithm for reducing monadic existential secondorder logic
formulae to equivalent simpler formulae, often firstorder logic
formulae. It is provably impossible for such a reduction to firstorder
logic to be always successful, even if there is an equivalent
firstorder formula for a secondorder logic formula. In this paper we
show that SCAN successfully computes the firstorder equivalents of all
Sahlqvist formulae in the classical (multi)modal language.
by D. M. Gabbay, R. A. Schmidt, and A. Szalas.
Studies in Logic: Mathematical Logic and Foundations,
Vol. 12,
College Publications
(2008).
ISBN 9781904987567.
BiBTeX,
Backcover,
Publisher's info.
Order at amazon.co.uk,
Order at amazon.com,
Order at amazon.de.

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.
SCAN Home
Forms:
Basic Form 
Correspondences Form 
Circumscription Form 
Help
Documentation:
Theory 
Computing Correspondences 
Computing Circumscription 
The System 
Conventions 
Syntax 
Literature
Maintained by
schmidt@cs.man.ac.uk.
Last modified: 05 Aug 13