A Process Logic for Querying  Graphs

Philippa Gardner

With the advent of XML and associated systems, there is much activity
in the development of semi-structured data models and languages for
accessing data on the Web. The basic structure for describing such
data is labelled directed graphs, as argued by Abiteboul, Buneman and
Suciu.  In this talk, I will give a simple process algebra for
describing these graphs, and introduce a process logic for reasoning
about such graphs.  This work evolved from two pieces of research:
Cardelli and Ghelli's language for querying labelled trees, using
ideas from the ambient calculus and ambient logic of Cardelli and
Gordon; and Gardner and others' use of process algebra to provide a
direct, compositional description of graphs. In this current work we
combine forces to provide a process logic for querying graphs.  Our
ultimate aim is to use our logic to provide a query language for
analysing such data, with a smooth integration between the data model,
logic and query language.

This work is joint with Luca Cardelli and Giorgio Ghelli. It is also
strongly influenced by Gardner's recent work with Lucian Wischik.