hide
Free keywords:
-
Abstract:
Many problems in computer science can be reduced to proving the satisfiability
of conjunctions of literals w.r.t. a background theory. This theory can be a
concrete theory (e.g. the theory of real or rational numbers), the extension of
a theory with additional functions (free, monotone, or recursively defined) or
a combination of theories. It is therefore very important to have efficient
procedures for checking the satisfiability of conjunctions of ground literals
in such theories.
We here give an overview of results on hierarchical and modular reasoning in
complex theories. We show that for a special type of extensions of a base
theory, which we call local, hierarchic reasoning is possible (i.e. proof tasks
in the extension can be hierarchically reduced to proof tasks w.r.t. the base
theory). Many theories important for computer science or mathematics fall into
this class (typical examples are theories of data structures, theories of free
or monotone functions, but also functions occurring in mathematical analysis).
In fact, it is often necessary to consider complex extensions, in which various
types of functions or data structures need to be taken into account at the same
time. We show how such local theory extensions can be identified and under
which conditions locality is preserved when combining theories, and we
investigate possibilities of efficient modular reasoning in such theory
combinations.
We present several examples of application domains where such theories occur in
a natural way. We show, in particular, that various phenomena analyzed in the
verification literature can be explained in a unified way using the notion of
locality.
