ETD system

Electronic theses and dissertations repository


Tesi etd-05112012-073755

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