Themen für Diplomarbeiten und individuelle Projekte

 

Liebe Studentinnen und Studenten,

im Folgenden stellen wir Ihnen einige Themen der Abteilung Formale Sprachen für Studien- bzw. Diplomarbeiten kurz vor. Falls Sie Interesse an einem der genannten Themen haben, sprechen Sie bitte die genannte Kontaktperson an, die Sie gerne genauer über dieses Thema informieren wird. Mit dieser können Sie auch klären, inwieweit Sie ein Thema bearbeiten können, falls sie (noch) nicht alle empfohlenen Vorkenntnisse besitzen.

Von Interesse sind auch die Leitfäden zur Durchführung von Diplomarbeiten und Individuellen Projekten, die Studierenden eine Orientierungshilfe geben sollen.

Derzeit bietet die Abteilung Formale Sprachen Themen zu den folgenden Bereichen an.

 

1 Grafische Konsistenzbedingungen

Grafische Konsistenzbedingungen sind ein geeignetes Mittel um (Eigenschaften von) Graphen zu beschreiben. Wenn Graphen zur Modellierung von Systemen eingesetzt werden, können mit Konsistenzbedingungen erwünschte bzw. unerwünschte Systemzustände beschrieben werden. In regelbasierten Systemen ist es möglich Konsistenzbedingungen in Anwendungsbedingungen zu transformieren, so dass Übergänge in nicht erlaubte Systemzustände unterbunden werden.

In diesem Zusammenhang bieten wir die folgenden Themen an:

1.1 Transformation von Konsistenzbedingungen in schwächste Vorbedingungen

Typ	Diplomarbeit (6 Monate).
Kontaktperson	Annegret Habel
Startzeitpunkt	ab sofort
Kandidat	Offen
Kurzbeschreibung	Ziel der Arbeit ist der Entwurf und die Programmierung einer Methode in Java, die als Parameter ein Graphprogramm und eine Konsistenzbedingung erhält und eine schwächste Vorbedingungung konstruiert. Ein wesentlicher Teil der bei der Implementierung benötigten Klassen und Methoden wird durch ein System zur Transformation von Konsistenz- in Anwendungsbedingungen [Zuc-06a] bereitgestellt. Auf Wartbarkeit, Erweiterbarkeit und Dokumentation des Gesamtergebnis wird bei diesem Projekt größten Wert gelegt.
Voraussetzungen	Kenntnisse in theoretischer Informatik, gute Kenntnisse in Softwaretechnik, gute Programmierfähigkeiten in Java.
Literatur	[HP-05] [EEHP-06] [Zuc-06a]

1.2 Spezifikation von regelbasierten Systemen: Eine Fallstudie

Typ	Diplomarbeit (6 Monate) oder Studienarbeit (4 Monate).
Kontaktperson	Annegret Habel
Startzeitpunkt	ab sofort
Kandidat	Offen
Kurzbeschreibung	Ziel dieser Arbeit ist die Entwicklung und Präsentation eines Beispiels für eine (abstrahierende) Modellierung eines Realweltsystems durch Transformationsregeln und Konsistenzbedingungen. Dabei wird das dynamische Verhalten durch Transformationsregeln modelliert, während Konsistenzbedingungen erwünschte Systemzustände beschreiben. Die Konsistenzbedingungen sollen in Anwendungsbedingungen für obige Regeln transformiert werden, so dass nur Übergänge in erlaubte Systemzustände möglich sind.
Voraussetzungen	Gute Kenntnisse über Graphersetzungssysteme.
Literatur	[HP-05] [EEHP-06]

 

2 Formale Sprachen

Im Bereich Formale Sprachen bieten wir folgendes Thema an:

2.1 FS-Visio: Visualisierung von Algorithmen für kontextfreie Grammatiken

Typ	individuelles Projekt (mit praktischem Anteil), Studienarbeit
Kontaktperson	Annegret Habel
Startzeitpunkt	ab sofort
Kandidat	Offen
Kurzbeschreibung	Ziel dieser Arbeit ist die Implementierung und visuelle Darstellung einiger bekannter Algorithmen aus dem Bereich Formale Sprachen als Java-Applet. Die Benutzerschnittstelle besteht sowohl aus einer einfachen Oberfläche zur Ausgabe der Ergebnisse, als auch aus der didaktisch aufbereiteten, interaktiven, gegebenfalls grafischen Darstellung der Arbeitsweise dieser Algorithmen. Das Ergebnis soll sich in die in Vorläufer-Projekten entwickelte Software FS-Visio einfügen, die insbesondere die Schnittstelle zur Dateneingabe bereitstellt. Die für dieses Projekt benötigten Methoden sollen soweit wie möglich auf vorhandene Klassenbibliotheken abgebildet werden. Auf Wartbarkeit, Erweiterbarkeit und Dokumentation des Gesamtergebnis (System- und Benutzerdokumentation, insbesondere Kommentierung der Quellen) wird bei diesem Projekt größten Wert gelegt.
Voraussetzungen	Gute Kenntnisse in theoretischer Informatik II, gute Kenntnisse in Softwaretechnik, gute Programmierfähigkeiten in Java.
Literatur	[HMU-01] [AU-72] [Hil-05] [Zuc-06b]

 

3 Literatur

[AU-72]

Alfred V. Aho and Jeffrey D. Ullman. The theory of parsing, translation, and compiling. Volume I: Parsing. Prentice Hall, 1972.

[AHPZ06]

Karl Azab, Annegret Habel, Karl-Heinz Pennemann, and Christian Zuckschwerdt. ENFORCe: A system for ensuring formal correctness of high-level programs. In Prelim. Proc. 3rd International Workshop on Graph Based Tools (GraBaTs'06), 2006.

[EEHP06]

Hartmut Ehrig, Karsten Ehrig, Annegret Habel, and Karl-Heinz Pennemann. Theory of constraints and application conditions: From graphs to high-level structures. Fundamenta Informaticae, 2006. To appear. Download [200 KB].

[Hil-05]

Rainer Hilbrands. FS-Visio: Visualisierung von Algorithmen für kontextfreie Grammatiken. Individuelles Projekt. September 2005.

[HMU-01]

John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman. Einfhrung in die Automatentheorie, Formale Sprachen und Komplexität. 2. Auflage, Pearson Studium, 2002.

[HP05]

Annegret Habel and Karl-Heinz Pennemann. Nested Constraints and Application Conditions for High-Level Structures. In Hans-Jörg Kreowski, Ugo Montanari, Fernando Orejas, Grzegorz Rozenberg, and Gabriele Taentzer, editors, Formal Methods in Software and System Modeling, volume 3393 of Lecture Notes in Computer Science. Springer-Verlag, 2005. Download [205 KB].

[HP06]

Annegret Habel and Karl-Heinz Pennemann. Satisfiability of high-level conditions. In Graph Transformations (ICGT'06), volume 4178 of Lecture Notes in Computer Science, pages 430-444, 2006. Download [188 KB].

[HP07]

Annegret Habel and Karl-Heinz Pennemann. Correctness of High-level Transformation Systems Relative to Nested Conditions. Submitted.

[HPR06]

Annegret Habel, Karl-Heinz Pennemann, and Arend Rensink Weakest preconditions for high-level programs. In Graph Transformations (ICGT'06), volume 4178 of Lecture Notes in Computer Science, pages 445-460. Springer-Verlag, 2006. Download [286 KB].

[HP-01]

Annegret Habel and Detlef Plump. Computational completeness of programming languages based on graph transformation. In Proc. Foundations of Software Science and Computation Structures (FOSSACS 2001), volume 2030 of Lecture Notes in Computer Science, pages 230-245. Springer-Verlag, 2001.

[Pen07]

Karl-Heinz Pennemann. An algorithm for approximating the satisfiability problem of high-level conditions. In Proc. Graph Transformation for Verification and Concurrency (GT-VC'07), Electronic Notes in Theoretical Computer Science, 2007. To appear. Long version: Download [412 KB].

[Zuc06a]

Christian Zuckschwerdt. Ein System zur Transformation von Konsistenz in Anwendungsbedingungen. Berichte aus dem Department für Informatik 11/06, 114 pages, Universität Oldenburg, 2006. Download [1.3 MB].

[Zuc-06b]

Christian Zuckschwerdt. Visualisierung von Earleys Algorithmus. Studienarbeit. März 2006.