Structured Operational Semantics for Graph Rewriting

Scientific Annals of Computer Science

article

A. Dorman¹  T. Heindel²  B. König³ 

[1] LIPN – UMR 7030, Universit´e Paris 13;CEA LIST, Institut CARNOT CEA LIST, DILS/LMEASI;Abteilung f¨ur Informatik und Angewandte Kognitionswissenschaft, Fachbereich Theoretische Informatik, Universit¨at Duisburg-Essen, Campus Duisburg, Fakult¨at f¨ur Ingenieurwissenschaften

关键词: process calculi;    graph transformation;    structural operational semantics;    compositional methods;   

DOI  :  10.7561/SACS.2012.1.105

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

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.

【 授权许可】

CC BY-ND