Copenhagen Programming Language Seminar


A Categorical Model of Computation for Graph Transformation: True Concurrency and Logic

Reiko Heckel ,
University of Leicester

Friday(!), December 1st, Time: 11:00 - 12:00(!) (!)
IT University of Copenhagen, Rued Langgaards Vej 7, 3A.12


Categories with algebraic structure are well-known as models of concurrent computations for, e.g., formal grammars, Petri nets, and term rewriting. The approach, of obtaining concurrent computations by means of an algebraic construction from a set of rules, can be generalised to graph transformation systems. The resulting computational model, a free double category with finite horizontal colimits, captures the established notion of concurrency of DPO graph transformation.

Such a construction exposes the intrinsic structure of concurrency in graph transformations and provides the basis for defining a temporal logic for concurrent computations. The logic represents a specialisation of van Benthem's arrow logic to categories, extended by spatial connectives like a concurrent composition of computations.

The talk will present the basics of the categorical model and discuss the definition of the logic, its semantics, deduction rules, and potential applications.

Scientific host: Lars Birkedal. Administrative host: Camilla Jensen. All are welcome.
The Copenhagen Programming Language Seminar (COPLAS) is a collaboration between DIKU, ITU and KVL.
COPLAS is sponsored by FIRST Graduate School.
To receive information about COPLAS talks by email, send a message to prog-lang-request@mail.it-c.dk with the word 'subscribe' as subject or in the body.

For more information about COPLAS, see http://www.coplas.org