Processes for Adhesive Rewriting Systems


Paolo Baldan, Andrea Corradini, Tobias Heindel, Barbara König, and Paweł Sobociński. Processes for adhesive rewriting systems. In Proc. of FOSSACS '06, pages 202–216. Springer, 2006. LNCS 3921.


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.

Suggested BibTeX entry:

    author = {Paolo Baldan and Andrea Corradini and Tobias Heindel and Barbara K{\"o}nig and Pawe{\l} Soboci\'{n}ski},
    booktitle = {Proc. of FOSSACS '06},
    note = {LNCS 3921},
    pages = {202--216},
    publisher = {Springer},
    title = {Processes for Adhesive Rewriting Systems},
    year = {2006}

PDF (335 kB)
© University of Duisburg-Essen, Theoretical Computer Science group