Baldan, Paolo; Corradini, Andrea; Heindel, Tobias; König, Barbara; Sobocinski, Pawel:
Processes for Adhesive Rewriting Systems
In: Proceedings of the 9th International Conference of Foundations of Software Science and Computation Structures, FOSSACS 2006. - (Lecture Notes in Computer Science ; 3921) - Berlin [u.a.]: Springer, 2006, S. 202 - 216
2006Buchaufsatz/Kapitel in Sammelwerk
Processes for Adhesive Rewriting Systems
Baldan, Paolo; Corradini, Andrea; Heindel, Tobias; König, BarbaraLSF; Sobocinski, Pawel


Rewriting systems over adhesive categories have been recently introduced as a general framework which encompasses several rewriting-based computational formalisms, including various modelling frameworks for concurrent and distributed systems. Here we begin the development of a truly concurrent semantics for adhesive rewriting systems by defining the fundamental notion of process, well-known from Petri nets and graph grammars. The main result of the paper shows that processes capture the notion of true concurrency-there is a one-to-one correspondence between concurrent derivations, where the sequential order of independent steps is immaterial, and (isomorphism classes of) processes. We see this contribution as a step towards a general theory of true concurrency which specialises to the various concrete constructions found in the literature.