Efficient Systems of Dynamic Interaction

A joint research project involving Imperial, King's, and University Colleges London.

EPSRC grants GR/L82441 (King's), GR/L85961 (UCL), GR/L85978 (Imperial).

The Research Project

The project is nominally to run from February 1998 until January 2000. Actually it is formally three projects, one for each site, with five staff: The aim of the project is to apply algebraic logic to solve problems in computer science.  The project will attempt:
  1. to capture the dynamic features of processes by designing tractable algebras of relations;
  2. to manage the interactions between the various dimensions in distributed and multi-agent systems by creating computationally well-behaved combinations of logic.

Modern computer systems involve dynamic interaction between various components. Naive logical modelling of dynamic interactions often leads to systems which are computationally more complex than the original problem. The aim of the project is to discover which aspects of such modellings cause intractability, and use this knowledge to design formal systems which faithfully reflect the complexity of the original problem, but are still expressive enough to capture its essential features.

We will undertake this research from both a logical and an algebraic perspective, and develop the mathematical methods as necessary for this. The general framework of combining logics was especially created to design systems which can capture different dimensions and their interactions. We will find out when interaction blocks transfer of tractability to the combinations, and use this knowledge to design tractable interactive systems. From the algebraic side, focussing on dynamic aspects of algebras of relations will allow us to develop algebras finely tuned for applications --- sufficiently expressive but not excessively complex.

The formalisms we develop will be evaluated with respect to both their theoretical complexity and their suitability for practical applications in the verification and specification of programs and distributed and multi-agent systems.