11 - Andrea Corradini: Subobject Transformation System and Elementary
Net Systems

[Joint work with Frank Hermann and Pawel Sobocinski] 

Abstract:

Subobject Transformation Systems (STS) are proposed as a novel formal
framework for the analysis of derivations of transformation systems
based on the algebraic, double-pushout approach.  They can be
considered as a simplified variant of DPO rewriting, acting in the
distributive lattice of subobjects of a given object of an adhesive
category. 

Interestingly, it turns out that STSs in the category of sets
with rules having empty interfaces correspond precisely to
Elementary Net System, a class of Petri nets widely studied in
the literature.

The formal setting of STSs allows a direct analysis of all possible
notions of dependency between any two productions without requiring an
explicit match.  In particular, several equivalent characterizations
of independence of productions are proposed, as well as a local
Church-Rosser theorem in the setting of STS. Also, we show how any
derivation tree in an ordinary DPO grammar leads to an STS via a
suitable construction, and we argue that relational reasoning in the
resulting STS is sound and complete with respect to the independence
in the original derivation tree.

From a methodological perspective, the relationship with ENSs could
provide challenging intuitions that could be generalized, at least in
part, to the more abstract setting of transformation systems over
adhesive categories.