Computer Science – Logic in Computer Science
Scientific paper
2011-08-02
EPTCS 59, 2011, pp. 37-51
Computer Science
Logic in Computer Science
In Proceedings ICE 2011, arXiv:1108.0144
Scientific paper
10.4204/EPTCS.59.4
Process calculi and graph transformation systems provide models of reactive systems with labelled transition semantics. 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. The first result is its equivalence with the so-called Borrowed Context technique. Unfortunately, the axiomatization is not compositional in the expected manner as no rule captures "internal" communication of sub-systems. The main result states that such a rule is derivable if the given graph transformation system enjoys a certain property, which we call "complementarity of actions". Archetypal examples of such systems are interaction nets. We also discuss problems that arise if "complementarity of actions" is violated.
Dorman Andrei
Heindel Tobias
No associations
LandOfFree
Structured Operational Semantics for Graph Rewriting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Structured Operational Semantics for Graph Rewriting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structured Operational Semantics for Graph Rewriting will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-508363