• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Document preview thumbnail
Preview 4 out of 258 pages
Other

Certifying Rule-Based Models Using Graph Transformation – Computer Science Study Notes and Research PDF

Document preview thumbnail
Preview 4 out of 258 pages

# Certifying Rule-Based Models Using Graph Transformation Explore the methods and concepts involved in certifying rule-based models through graph transformation techniques. This academic resource is relevant to computer science, formal methods, model-driven engineering, and software verification. The material may cover topics such as: - Rule-based modelling and graph transformation systems - Graph rewriting rules and transformation processes - Formal verification and model correctness - Certification of rule-based systems - Properties, constraints, and consistency checking - Applications of graph transformation in software engineering **Ideal for:** Computer science students, software engineering researchers, and learners studying formal methods, graph rewriting, and model verification. Use this resource to support your understanding of how graph transformation techniques can help establish the correctness and reliability of rule-based models.

Content preview

Certifying Rule-Based Models
using Graph Transformation


vorgelegt von
Diplom-Mathematikerin
Leen Lambers



Fakultät IV — Elektrotechnik und Informatik
der Technischen Universität Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
Dr. rer. nat
genehmigte Dissertation




Promotionsausschuss:
Vorsitzende: Prof. Dr. Sabine Glesner
Berichter: Prof. Dr. Hartmut Ehrig
Berichter: Prof. Dr. Fernando Orejas
Berichterin: Prof. Dr. Gabriele Taentzer




Tag der wissenschaftlichen Aussprache: 30. Oktober 2009




Berlin 2010

D 83

,Abstract
Many systems exhibit rule-based behavior that can be modeled very well by means of graph
transformation. In this thesis, a new graph transformation theory is introduced for a more
expressive kind of graph transformation than the usual one. This kind of graph transfor-
mation not only allows positive pre- and post-conditions to be expressed in rules, but also
allows so-called negative application conditions. Present analysis techniques are extended
for this more expressive kind of graph transformation. These techniques allow, amongst
other things, the static detection of potential conflicts and causal dependencies between
transformations, and the detection of local confluence in cases of conflicts. For this pur-
pose, the theory of critical pairs is extended. Moreover, new kinds of analysis techniques
are introduced and present techniques are improved. One new technique enables, for exam-
ple, the static analysis of applicability (resp. non-applicability) of rule sequences. The main
part of the newly developed theory in this thesis does not only apply to graph transforma-
tion. In addition, it is formulated in the more abstract adhesive high-level-transformation
framework. Consequently, the analysis techniques can be applied not only to graphs, but
also to other complex structures such as, for example, Petri nets and attributed graphs. Fi-
nally, a general road map is presented leading to the certification of a selection of properties
in rule-based models. The certification, based on graph transformation analysis techniques,
is illustrated by a case study of an elevator control system. Moreover, the current tool sup-
port for certification of rule-based models using graph transformation provided by AGG is
outlined.

,Zusammenfassung
Viele Systeme zeigen regelhaftes Verhalten auf was sehr gut durch Graphtransformation
modelliert werden kann. Diese Dissertation führt eine neue Graphtransformationstheorie
für eine ausdruckskräftigere Variante von Graphtransformation als die bisherige ein. Sie
erlaubt nicht nur positive Vor- und Nachbedingungen in Regeln, sondern auch negative
Anwendungsbedingungen. Die bisherigen Analysetechniken werden erweitert für diese
ausdruckskräftigere Variante. Diese Techniken ermöglichen unter anderem das statische
Aufspüren von potentiellen Konflikten oder kausalen Abhängigkeiten zwischen Transfor-
mationen, und das Feststellen von lokaler Konfluenz im Falle eines Konflikts. Zu diesem
Zweck wurde die Theorie der kritischen Paare erweitert. Es werden auch neuartige Analy-
setechniken eingeführt und die bisherigen werden teilweise effizienter gemacht. Eine der
neuen Techniken ermöglicht zum Beispiel eine statische Prüfung der Anwendbarkeit bzw.
Nicht-Anwendbarkeit von Regelsequenzen. Der Hauptteil der entwickelten Theorie in die-
ser Dissertation ist nicht nur auf Graphtransformationen anwendbar. Sie wird ausserdem
formuliert im abstrakteren Rahmenwerk der adhesiven High-Level-Transformation. Somit
können die Analysetechniken nicht nur auf Graphen, sondern auch auf andere komplexe
Strukturen sowie z.B. Petrinetze und attributierte Graphen angewandt werden. Schliesslich
wird eine allgemeine Vorgehensweise vorgeschlagen, die zur Zertifizierung einer Auswahl
von Eigenschaften der regelbasierten Modelle führt. Die Zertifizierung, basierend auf Ana-
lysetechniken für Graphtransformation, wird illustriert am Fallbeispiel einer Fahrstulkon-
trolle. Ausserdem wird die aktuelle Werkzeugunterstützung in AGG, hinsichtlich der Zer-
tifizierung von regelbasierten Modellen mittels Graphtransformation, vorgestellt.

,Acknowledgements
Writing this thesis was a challenge that I was able to accept, by and by, thanks to the
encouragement of several people accompanying me during the last few years.
In particular, I would like to thank . . .
Hartmut Ehrig, for the continuous monitoring of this thesis and for giving me the oppor-
tunity to work in your group, benefit from your wealth of experience, and learn from the
accuracy and intensity that you apply when doing research.
Fernando Orejas, for enabling my research stays at the UPC in Barcelona where we had
several inspiring discussions, providing a solid basis for joint work and encouraging me to
keep working on many subjects elaborated in this thesis.
Gabriele Taentzer, for your valuable comments with regard to this thesis, for believing
in my skills, and for being such an animating counterpart. I hope to be able to continue
our close cooperation in the near future. In this regard, many thanks also to Stefan Jurack
and Katharina Mehner for our productive Berlin-Marburg-Munich collaboration during the
past two years.
Mauro Pezzè, for facilitating my research stay in your group at the university of Milano,
Bicocca, where you gave me the opportunity to report on my research and to learn about
inventive applications developed in your lab. In this regard, special thanks also to Leonardo
Mariani, for the fruitful cross-border cooperation beyond my stay and to all members of
the lab, for being such welcoming interim colleagues.
Annegret Habel, for our recently started cooperation – in the middle of writing up this
thesis. I look forward to continuing our joint work.
The many friendly and inspiring colleague researchers of the graph transformation com-
munity that I met during conferences, workshops, and research stays, making these gath-
erings to memorable and motivating experiences.
My colleagues in Berlin, with whom I share – or shared – daily working life, for your
companionship during seminars, co-authoring papers, teaching, TFS breakfasts, coffee
breaks, floor chats, . . . . Special thanks to Claudia Ermel, Ulrike Prange, and Alexander
Rein for carefully proofreading parts of this thesis, and to Olga Runge, for being so hard-
working when implementing new features in AGG. Thank you to Käte Schlicht, for your
support concerning all kinds of administrative matters. Moreover, many thanks to Maria
Oswald and Margit Russ, for the enjoyable joint time as office mates.
My friends, for having fun with me and encouraging me, and giving me timely distrac-
tions from graph transformation and all that kind of stuff. Special thanks to Mieke, for
your professional advice with regard to the musical example in the introduction.
My family, and in particular, my parents, for presenting me with an always welcoming
home, helping me to hang in there: ”bedankt”.
Daniel, for giving me the special kind of energy needed to bring this thesis to an end.

Document information

Uploaded on
November 21, 2026
Number of pages
258
Written in
2026/2027
Type
Other
Person
Unknown
$19.99

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
Maliah
3.6
(18)
Sold
93
Followers
39
Items
2004
Last sold
4 days ago



Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their tests and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can instantly pick a different document that better fits what you're looking for.

Pay as you like, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions