Lehrveranstaltung im Wintersemester 2011/2011

Formale Sprachen: Graphtransformation

Master-Basis-Kurs(4 SWS) in Theoretischer Informatik (auch Diplom-Hauptstudium)

(VAK 03-MB-603.01/1, Kategorie: V, Voraussetzungen: 601.01, 601.02, ECTS: 6, TMG: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
  Mo von 16:00 - 18:00 MZH 1090
- K 2 SWS
  Mi von 14:00 - 16:00 GW2 B1400

Skript zur Veranstaltung
- Grundlagen der Graphtransformation (pdf): Hans-Jörg Kreowski, Renate Klempien-Hinrichs, Sabine Kuske: Some Essentials of Graph Transformation. In Z. Esik, C. Martin-Vide, V. Mitrana, editors, Recent Advances in Formal Languages and Applications, volume 25 of Studies in Computational Intelligence, pages 229-254. Springer, 2006.
- Graphtransformationseinheiten (pdf): Hans-Jörg Kreowski, Sabine Kuske, Grzegorz Rozenberg: Graph Transformation Units - An Overview. In: Pierpaolo Degano, Nicola De Rocco, Josi Meseguer (Eds.): Concurrency, Graphs and Models, Essays Dedicated to Ugo Montanari on the Occasion of His 65th Birthday, Lecture Notes in Computer Science, Vol. 5065, 2008, 19 pages, to appear.
- Eine graphtransformatorische Version der while-Programmierung (pdf): Hans-Jörg Kreowski, Karsten Hölscher, Peter Knirsch: Semantics of Visual Models in a Rule-based Setting. In R. Heckel, editor, Proceedings of the School of SegraVis Research Training Network on Foundations of Visual Modelling Techniques (FoVMT 2004), Dagstuhl, volume 148 of Electronic Notes in Theoretical Computer Science, pages 75-88. Elsevier Science, 2006.

Weitere Materialien
- Graphen und ihre Ableitung (pdf, pdf verkleinert)
- Kapitel Hyperkantenersetzung (pdf):
  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.


	Research Group Theoretical Computer Science
	Lehrveranstaltung im Wintersemester 2011/2011 Formale Sprachen: Graphtransformation Master-Basis-Kurs(4 SWS) in Theoretischer Informatik (auch Diplom-Hauptstudium) (VAK 03-MB-603.01/1, Kategorie: V, Voraussetzungen: 601.01, 601.02, ECTS: 6, TMG: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 Mo von 16:00 - 18:00 MZH 1090 K 2 SWS Mi von 14:00 - 16:00 GW2 B1400 Skript zur Veranstaltung Grundlagen der Graphtransformation (pdf): Hans-Jörg Kreowski, Renate Klempien-Hinrichs, Sabine Kuske: Some Essentials of Graph Transformation. In Z. Esik, C. Martin-Vide, V. Mitrana, editors, Recent Advances in Formal Languages and Applications, volume 25 of Studies in Computational Intelligence, pages 229-254. Springer, 2006. Graphtransformationseinheiten (pdf): Hans-Jörg Kreowski, Sabine Kuske, Grzegorz Rozenberg: Graph Transformation Units - An Overview. In: Pierpaolo Degano, Nicola De Rocco, Josi Meseguer (Eds.): Concurrency, Graphs and Models, Essays Dedicated to Ugo Montanari on the Occasion of His 65th Birthday, Lecture Notes in Computer Science, Vol. 5065, 2008, 19 pages, to appear. Eine graphtransformatorische Version der while-Programmierung (pdf): Hans-Jörg Kreowski, Karsten Hölscher, Peter Knirsch: Semantics of Visual Models in a Rule-based Setting. In R. Heckel, editor, Proceedings of the School of SegraVis Research Training Network on Foundations of Visual Modelling Techniques (FoVMT 2004), Dagstuhl, volume 148 of Electronic Notes in Theoretical Computer Science, pages 75-88. Elsevier Science, 2006. Weitere Materialien Graphen und ihre Ableitung (pdf, pdf verkleinert) Kapitel Hyperkantenersetzung (pdf): 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.	Mail Address University of Bremen Dept. for Math. & Computer Science P.O. Box 330 440 28334 Bremen Germany Physical Address Linzer Strasse 9a OAS 3002 28359 Bremen Phone ++49(421)218 64450 Fax ++49 (421) 218 4322 Email (Secr.) Helga Reinermann helga@tzi.de
		© / 07.10.11