Working group: "Computational Biology"

2010, the 26th of October

Tobias Heindel

Title: Rewriting steps instead of letters, transitions and reactions

Abstract:

Certain (types of) events in action based systems might occur in any order if they are not causally dependent on each other, i.e. concurrent. The talk begins with a review of Mazurkiewicz traces and Petri nets, which are well-known models of concurrency. It continues with the generalisation to graph grammars and the so-called Sequential Commutativity Theorem, which describes the non-trivial exchange of ``concurrent'' pairs of consecutive graph rewriting steps -- the counterpart of letters and transition (occurrences) in Mazurkiewicz traces and Petri nets, respectively.

The Sequential Commutativity Theorem is a basic theorem of graph transformation and will allow to explain the role of adhesive categories and its variants (including the partial map adhesive ones), which will be discussed in the second half of the talk. Depending on the time constraints and the preferences of the audience, the talk could conclude with a conceptually simple, fundamental category theoretical characterization of partial map adhesive categories and/or a discussion about (the potential of) a graph transformation counterpart of kappa-calculus reactions.