In essence, modal logic is a simple formalism for working with relational structures (or multigraphs). But modal logic has no mechanism for referring to or reasoning about the individual nodes in such structures, and this lessens its effectiveness as a representation formalism. In their simplest form, hybrid logics are upgraded modal logics in which reference to individual nodes is possible.

But hybrid logic is a rather unusual modal upgrade. It pushes one simple idea as far as it will go: represent all information as formulas. This turns out to be the key needed to draw together a surprisingly diverse range of work (for example, feature logic, description logic and labelled deduction). Moreover, it displays a number of knowledge representation issues in a new light, notabley the importance of sorting.

Relevant Material:

1.

The slides of the talk.

2.

P. Blackburn (2000) Representation, Reasoning, and Relational Structures: a Hybrid Logic Manifesto. Proc. of the 1st. Method for Modalities Workshop. Amsterdam. Areces, C., Franconi, E., Goré, R., de Rijke, M., Schlingloff, H., editors. Special Issue of the Logic Journal of the IGPL. Vol 8:3, 339-625.

But the basic hybrid language also has an excellent behavior in terms of complexity: the addition of nominals and @ to the basic modal logic K enhace its expressive power without modifying its complexity (except, perhaps, by a polynomial).

In this talk we will introduce model theoretic tools to investigate the complexity of the basic hybrid language and its multi-modal and tense logical cousins.

Relevant Material:

1.

C. Areces, P. Blackburn and M. Marx (1999). A Road-map on Complexity for Hybrid Logics. In J. Flum and M. Rodríguez-Artalejo, editors, Proc. of the 8th Annual Conference of the EACSL, Madrid.

2.

C. Areces, P. Blackburn and M. Marx (1999) The Computational Complexity of Hybrid Temporal Logics. To appear in the Logic Journal of the IGPL.