Graphs and Graph Transformations for Object-Oriented and Service-Oriented Systems

Theories of graphs and graph transformations form an important part of the mathematical foundations of computing, and have been applied in a wide range of areas from the design and analysis of algorithms to the formalization of various computer systems and programs. In this thesis, we study how graphs and graph transformations can be used to model the static structure and dynamic behavior of object-orientated and service-oriented systems. Our work is mainly motivated by the difficulty in understanding and reasoning about objectorientated and service-oriented programs, which have more sophisticated features compared with traditional procedural programs. We show that the use of graphs and graphs transformations provides both an intuitive visualization and a formal representation of object-orientated and serviceoriented programs with these features, improving people’s understanding of the execution states and behaviors of these programs. We provide a graph-based type system, operational semantics and refinement calculus for an object-oriented language. In this framework, we define class structures and execution states of oo programs as directed and labeled graphs, called class graphs and state graphs, respectively. The type system checks whether a program is well-typed based on its class graph, while the operational semantics defines each step of program execution as a simple graph transformations between state graphs. We show the operational semantics is type-safe in that the execution of a well-typed program does not “go wrong”. Based on the operational semantics, we study the notion of structure refinement of oo programs as graph transformations between their class graphs. We provide a few groups of refinement rules for various purposes such as class expansion and polymorphism elimination and prove their soundness and relative completeness. We also propose a graph-based representation of service-oriented systems specified in a serviceoriented process calculus. In this framework, we define states of service-oriented systems as hier- archical graphs that naturally capture the hierarchical nature of service structures. For this, we exploit a suitable graph algebra and set up a hierarchical graph model, in which graph transformations are studied following the well-known Double-Pushout approach. Based on this model, we provide a graph transformation system with a few sets of graph transformation rules for various purposes such as process copy and process reduction. We prove that the graph transformation system is sound and complete with respect to the reduction semantics of the calculus.