An Abstract Model of Hierarchical Graphs and
Hierarchical Graph Transformation
Giorgio Busatto
An Abstract Model of
Hierarchical Graphs and
Hierarchical Graph Transformation
von Giorgio Busatto
Dissertation
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
Vorgelegt im Fachbereich 17 (Informatik)
der Universit¨at Paderborn
im Januar 2002
Datum des Promotionskolloquiums: 21. Juni 2002
Gutachter: Prof. Dr. Gregor Engels
Prof. Dr. Hans-J¨org Kreowski
Prof. Dr. Wilhelm Sch¨afer
Diese Arbeit ist als Nr. 3/02 in der Reihe “Berichte aus dem Fachbereich Informatik” (ISSN
0946-2910) des Fachbereichs Informatik der Carl von Ossietzky Universit¨at Oldenburg er-
schienen.
Abstract
Hierarchical graphs are an extension of ordinary graphs used to describe structural
information—like grouping and encapsulation—that cannot be modeled “naturally” by
means of flat graphs. Motivated by different application areas, many approaches to hi-
erarchical graphs and their transformation exist in the literature. These share common
concepts but provide different notions, and often deal with unessential, application-
specific aspects.
In the present thesis, we propose an abstract model of hierarchical graphs and their
transformation that tries to capture these common concepts, and to distinguish them
from other aspects. This should help to better understand and to compare existing
approaches, and allow to define new notions of hierarchical graphs. Rather than a
specific approach, we propose a generic framework that must be instantiated in order
to define concrete models.
The framework supports hierarchical graphs with many different kinds of underlying
graphs (e.g. attributed, labelled, directed, undirected, hypergraphs), different kinds
of hierarchies (tree-like, dag like, arbitrary), and provides typing and encapsulation.
Operations are specified in a rule-based fashion: Hierarchical graph transformation
rules are a combination of existing flat graph transformation rules. In this respect, our
model can be considered an extension of the well-known notion of graph transformation.
We have instantiated our framework using a particular graph transformation
approach—the double-pushout—and we have investigated the properties of the result-
ing model. On the practical side, we have applied this model for specifying consistent
operations on hypermedia structures in a concrete case study.
By comparing it to other known approaches in the graph transformation field, we
can show that our framework covers the static aspects of all the considered notions, and
can simulate the behaviour of several of them. A wider investigation of the dynamic
aspects of related approaches, especially of those outside the graph-grammar field, is an
interesting topic for future research. Other directions for future research include a more
powerful transformation mechanism, encapsulated hierarchical graph transformation,
and further investigation on the applicability of our model in the hypermedia or in
other practical fields.
Acknowledgements
In this small space I would like to remember many persons that in different—sometimes
indirect—ways contributed to a successful completion of the present thesis.
First of all I wish to thank Gregor Engels for giving me the opportunity to write
this thesis, and for constantly following and supporting my work. His supervision was
essential for educating my skills as a researcher, for motivating me, and for completing
this work successfully.
I also wish to thank Hans-J¨org Kreowski: it was a pleasure and a stimulating experi-
ence to work with him during my stay in Bremen. The friendly and familiar atmosphere
in his research group offered me an excellent working environment.
I also would like to acknowledge the contribution of the European research network
GEneral Theory of GRAph Transformation Systems (GETGRATS) and its coordinator
Andrea Corradini for supporting a considerable part of the research presented in this
thesis.
A special thank goes to Berthold Hoffmann for reading the preliminary versions of
the thesis and for his constant support, and to Annegret Habel for her advice and help
during the preparation for my defense. I also wish to remember my ex-colleagues and
friends Dmitri½ Qeresiz, Katharina Mehner, Peter Knirsch, Pieter Jan ’t Hoen, Ray
Dassen, Renate Klempien-Hinricks, Sabine Kuske, Vincent Zweije. A special mention
to Sebastian Maneth for our many full-fledged joint discussions.
Also, bedankt to Alessandro for introducing me to the most diverse languages and
to bagna kouda, to Michela for her dear friendship and unforgotten support during my
first period abroad, to Luigi, Sara and Karl for so many reasons that do not fit in this
page, and to Francesco for always suggesting a new wind to fly.
Grazie to my parents Francesco and Rina for supporting my study and for encour-
aging me when I began my adventure abroad, and to my sister Laura for her constant
affection. I also thank my grandparents Lodovico and Maria, to whose dear memory
this work is dedicated, for teaching me to laugh and to see fun and paradox in life and
in people.
Einen speziellen Dank an Nataxa und Vladik f¨ur ihr gutes Herz und liebste
Freundschaft, das Erdbeben, und alles.
Finally, I wish to thank all the musicians that kept me going during these years:
Bach, Elio e le Storie Tese, Josquin, Monteverdi, Mozart, Palestrina, The Cranberries,
Vivaldi, and many others.
Loading more pages...