We generalise both the notion of a non-sequential process and the unfolding construction (which was previously developed for concrete formalisms such as Petri nets and graph grammars) to the abstract setting of (single pushout) rewriting of objects in adhesive categories. The main results show that processes are in one-to-one correspondence with switch-equivalent classes of derivations, and that the unfolding construction can be characterised as a coreflection, that is, 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 ω-chains of monos. Compared with 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.

Processes and unfoldings: concurrent computations in adhesive categories

CORRADINI, ANDREA;
2014

Abstract

We generalise both the notion of a non-sequential process and the unfolding construction (which was previously developed for concrete formalisms such as Petri nets and graph grammars) to the abstract setting of (single pushout) rewriting of objects in adhesive categories. The main results show that processes are in one-to-one correspondence with switch-equivalent classes of derivations, and that the unfolding construction can be characterised as a coreflection, that is, 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 ω-chains of monos. Compared with 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.
Baldan, P.; Corradini, Andrea; Heindel, T.; Koenig, B.; Sobocinski, P.
File in questo prodotto:
File Dimensione Formato  
2014-MSCS-POST-ProcessesAndUnfoldings-ConcurrentComputationsInAdhesiveCategories.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 677.31 kB
Formato Adobe PDF
677.31 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/581868
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact