University of Bremen Logo  
 
Research Group Theoretical Computer Science
 
HOME
TEAM
TEACHING
RESEARCH

Lehrveranstaltung im Sommersemester 2004

Formale Sprachen: Graphtransformation

Kurs (4 SWS) im Modulbereich Theorie

(VAK 03-603.02, Kategorie: V, ECTS: 6)


Die Syntax von Programmier-und Spezifikationssprachen traditioneller Art, die textuell basiert sind, lässt sich erfolgreich mit Hilfe von Chomsky-Grammatiken und insbesondere kontextfreien Grammatiken beschreiben. Für die Syntaxbeschreibung visueller Sprachen, bei denen die wesentlichen Elemente bildhaft und diagrammatisch sind (wie beispielsweise bei der objektorientierten Modellierungssprache UML), fehlt noch eine allgemein anerkannte methodische Grundlage. In der Lehrveranstaltung wird systematisch dargelegt und erarbeitet, dass Graphtransformation, bei der Regeln nicht auf Zeichenketten, sondern Graphen operieren, eine brauchbare und adäquate Basis für die syntaktische und darüber hinaus auch semantische Behandlung visueller Modellierungsmethoden sein kann. Insofern knüpft die Lehrveranstaltung an die aus dem Grundstudium bekannten Elemente formaler Sprachen an. Sie bildet gleichzeitig eine Vertiefung von Algorithmen auf Graphen, die ebenfalls mit Hilfe von Konzepten der Graphtransformation modelliert werden können. Die Teilnahme an dieser Lehrveranstaltung ist allerdings keine unbedingte Voraussetzung, da die erforderlichen Grundlagen nachgeholt werden können. Es wird ein Skript geben, das bisher nur teilweise vorliegt und während der Veranstaltung weiterentwickelt wird.


  • Skript zur Veranstaltung
    • Kapitel 1 und 2 (pdf, pdf verkleinert, ps, ps verkleinert)
    • Kapitel Hyperkantenersetzung (pdf, ps):
      Frank Drewes, Annegret Habel, Hans-Jörg Kreowski: Hyperedge Replacement Graph Grammars. In G. Rozenberg, Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 1: Foundations, chapter 2, pages 95-162. World Scientific, 1997.
    • Abschnitt Sortieren durch paralleles Vertauschen (pdf, ps)

  • Folien zur Veranstaltung
    • Graphgrammatik-Maschine (4. - 13. Mai) pdf
    • Modellierung (18. Mai) pdf
    • Hyperkantenersetzungsgrammatiken (25. & 27. Mai) pdf
    • Kontextfreiheitslemma (1. & 3. Juni) pdf
    • Parallelregeln und -ableitungen (22. & 24. Juni, 6. Juli) pdf
    • Petri-Netze (29. Juni & 1.Juli) pdf

  • Aufgabenblätter

  • Termine
    • K 2 SWS
      Di von 15:15 - 16:45 MZH 1400
    • K 2 SWS
      Do von 8:30 - 10:00 MZH 1400

Mail Address
University of Bremen
Dept. for Math. &
Computer Science

P.O. Box 330 440
28334 Bremen
Germany

Physical Address
Bibliothekstrasse 5
MZH 5130
28359 Bremen

Phone
++49(421)218 64451

Email (Secr.)
Helga Reinermann

helga@tzi.de