A new criterion for M,N-adhesivity, with an application to hierarchical graphs


The introduction of adhesive categories marked a watershed moment for the algebraic approaches to the rewriting of graph-like structures, as they provide an abstract framework where many general results can be recast and uniformly proved. However, checking that a category satisfies the adhesivity properties is sometimes far from immediate. In this talk we present a new criterion giving a sufficient condition for M,N-adhesivity, a generalisation of the original notion of adhesivity. We apply it to several existing categories, and in particular to hierarchical graphs, a formalism that is notoriously difficult to fit in the mould of algebraic approaches to rewriting and for which various alternative definitions float around.

Friday, June 17, 2022 15:00 Europe/Paris
GReTA seminar
Davide Castelnovo
Davide Castelnovo
PhD Student

In the last decades much attention has been devoted in Computer Science to extensions of classical or intuitionistic logic obtained adding additional operators besides the usual logical connectives and quantifiers (separation logic, the various flavours of spatial and temporal logics, bunched implication, etc…). This gives rise to the problem of how to provide models of such kinds of logics. To this end, several researchers have advocated the use categorical structures like fibrations, in line with the way in which category theory provides a semantics for the usual first order logic. My main aim is to provide an appropriate notion of model for some of this modal logic. Possibly deducing metatheoretic or proof-theoretic results like completeness.