SOS-Supported Graph Transformation

Abstract

In this paper, we propose a simplicity-oriented approach for model-tomodel transformations of graphical languages. Key to simplicity is decomposing the rule system into two rule sub-systems that separate purpose-specific aspects (transformation and computation), and specifying these rule systems as a graphical language. For the transformational aspect, we use a compiler-like generation approach, while taking Plotkin’s Structural Operational Semantics (SOS) as inspiration for the computational aspect. We define these rule systems as inference rules for pattern-based transformations of typed, hierarchical graphs. Using typed graphs allows patterns to easily distinguish between the elements of the source graph. The resulting rule system (named SOS-Supported Graph Transformation, or SOS-GT) supports a well-structured and intuitive specification of complex model-to-model transformations adequate for a variety of use cases. We illustrate these rules with an example of transforming the WebStory language (WSL, an educational tool) to a Kripke Transition System (KTS) suitable for model checking, and give an overview over more applications in the end of the paper.