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
Buchaufsatz / Kapitel / Fach: Informatik
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.