Unfolding Grammars in Adhesive Categories
P. Baldan(1), A. Corradini(2), T. Heindel(3), B. Koenig(3), P. Sobocinski(4)
(1) Dipartimento di Matematica Pura e Applicata, Università di Padova, Italy
(2) Dipartimento di Informatica, Università di Pisa, Italy
(3) Institut für Informatik und interaktive Systeme,
Universität Duisburg-Essen, Germany,
(4) ECS, University of Southampton, UK
Abstract:
We generalize the unfolding semantics, previously developed for
concrete formalisms such as Petri nets and graph grammars, to the
abstract setting of (single pushout) rewriting over adhesive
categories. The unfolding construction is characterized as a
coreflection, i.e. the unfolding functor arises as the right adjoint
to the embedding of the category of occurrence grammars into the
category of grammars. As the unfolding represents potentially
infinite computations, we need to work in adhesive categories with
"well-behaved" colimits of omega-chains of monomorphisms. Compared to
previous work on the unfolding of Petri nets and graph grammars, our
results apply to a wider class of systems, which is due to the use of
a refined notion of grammar morphism.