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

Lehrveranstaltung im Sommersemester 2006

Formale Sprachen: Graphtransformation

Kurs (4 SWS) im Modulbereich Theorie

(VAK 03-05-H-603.02, Kategorie: V, Voraussetzungen: 601.01, 601.02, 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. Als drittes Element wird das Thema Parallelität und Nebenläufigkeit behandelt. Es wird schriftliche Materialien geben, die den Stoff der Lehrveranstaltung weitgehend abdecken.


  • Termine
    • K 2 SWS
      Di von 15:15 - 16:45 SFG 2040
    • K 2 SWS
      Do von 8:30 - 10:00 SFG 1040

  • Skript zur Veranstaltung
    • Grundlagen der Graphtransformation (pdf):
      Hans-Jörg Kreowski, Renate Klempien-Hinrichs, Sabine Kuske:
      Some Essentials of Graph Transformation.
      In C. Martin-Vide, V. Mitrana, editors, Formal Languages and Applications.
      Springer, 2005. To appear.

  • Weitere Materialien
    • Literaturliste (ps)
    • Graphen und ihre Ableitung (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.
    • Regelbasierte Modellierung mit autonomen Transformationseinheiten (ps):
      Karsten Hölscher, Renate Klempien-Hinrichs, Peter Knirsch, Hans-Jörg Kreowski, Sabine Kuske: Regelbasierte Modellierung mit autonomen Transformationseinheiten. Technical Report 1, Universität Bremen, Fachbereich 3, 2005.
    • Picture generation by collage grammars (ps.gz):
      Frank Drewes, Hans-Jorg Kreowski: Picture generation by collage grammars. In H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg, Handbook of Graph Grammars and Computing by Graph Transformation. Vol. 2: Applications, chapter 11, pages 397-457. World Scientific, 1999.

  • Folien zur Veranstaltung
    Als Service: die Folien der vorangegangenen Veranstaltung. Der Stoff ist derselbe; es gibt kleine Unterschiede bezüglich der Notation und der Reihenfolge.
    • Graphgrammatik-Maschine pdf
    • Modellierung pdf
    • Hyperkantenersetzungsgrammatiken pdf
    • Kontextfreiheitslemma pdf
    • Parallelregeln und -ableitungen pdf
    • Petri-Netze pdf
    • Visuelle Modellierung und Modelltransformation pdf
    • Zelluläre Automaten pdf

  • Aufgabenblätter

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