Viorica Sofronie-Stokkermans
University Koblenz-Landau, Germany

Title: Hierarchical reasoning in local theory extensions and applications

Abstract:

Many problems in mathematics and computer science can be reduced to proving the satisfiability of conjunctions of literals in extensions and combinations of theories. It is therefore very important to identify situations where reasoning in complex theories can be done efficiently and accurately. Efficiency can be achieved for instance by reducing the search space (preferably without losing completeness) or by exploiting modularity – i.e. delegating some proof tasks which refer to a specific theory to provers specialized in handling formulae of that theory.

In this talk we will 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 applications — in mathematics, verification of reactive, real time and hybrid systems — where such theories occur in a natural way.