Processes for Adhesive Rewriting Systems

Paolo Baldan, Andrea Corradini, Tobias Heindel, Barbara König, Pawel Sobocinski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationFoundations of Software Science and Computation Structures
Subtitle of host publication 9th International Conference, FOSSACS 2006, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006, Vienna, Austria, March 25-31, 2006, Proceedings
PublisherSpringer Berlin Heidelberg
Pages202-216
Number of pages15
Volume3921
ISBN (Electronic)978-3-540-33046-2
ISBN (Print)978-3-540-33045-5
DOIs
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'Processes for Adhesive Rewriting Systems'. Together they form a unique fingerprint.

Cite this