Structured Operational Semantics for Graph Rewriting

Andrei Dorman, Tobias Heindel, Barbara König

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Process calculi and graph transformation systems provide models of reactive systems with labelled transition semantics (LTS). While the semantics for process calculi is compositional, this is not the case for graph transformation systems, in general. Hence, the goal of this article is to obtain a compositional semantics for graph transformation system in analogy to the structural operational semantics (SOS) for Milner's Calculus of Communicating Systems (CCS). The paper introduces an SOS style axiomatization of the standard labelled transition semantics for graph transformation systems that is based on the idea of minimal reaction contexts as labels, due to Leifer and Milner. In comparison to previous work on inductive definitions of similarly derived LTSs, the main feature of the proposed axiomatization is a composition rule that captures the communication of sub-systems so that it can feature as a counterpart to the communication rule of CCS.
Original languageEnglish
Pages (from-to)105-145
Number of pages41
JournalScientific Annals of Computer Science
Issue number1
Publication statusPublished - 2012


Dive into the research topics of 'Structured Operational Semantics for Graph Rewriting'. Together they form a unique fingerprint.

Cite this