Inhalt und Material

Inhalt

Regelbasierte Systeme definieren bin�re Relationen �ber Mengen von Objekten. Die Objekte stellen die m�glichen Zust�nde eines Systems dar, und die Relationen beschreiben die auf ihnen m�glichen Zustandsver�nderungen. Man kann einige fundamentale Eigenschaften regelbasierter Definitionen ganz abstrakt studieren, ohne die Art der Objekte oder Regeln zu kennen. F�r spezifischere Eigenschaften betrachtet man dann konkrete Objekte - W�rter, B�ume (Terme) oder Graphen - und verschiedene Formen von Regeln auf diesen Objekten. Regeln sind oft ausf�hrbar, k�nnen also dazu benutzt werden, einen Prototypen f�r ein System zu erzeugen. F�r solche Regeln wurden verschiedene regelbasierte Sprachen und Werkzeuge entwickelt, die f�r rapid prototyping und als Grundlage f�r die Entwicklung und Analyses von praktisch nutzbaren Computersystemen dienen k�nnen.

Inhalt

Titel und Inhaltsverzeichnis
Einf�hrung
Abstrakte Reduktion.
- Reduktion, Termination und Konfluenz
- Sprache, Ableitung und Erkennung
Wort
- W�rter und Sprachen
- Chomsky-Grammatiken
- van-Wijngaarden-Grammatiken
- Attribut-Grammatiken
- Zusatzquelle:
  1. A. Mateescu, A. Salomaa: Wijngaarden and Attribute Grammars, (Abschnitt 4 und 5 in Kapitel 4 "Aspects of Classical Language Theory" in G. Rozenberg, A. Salomaa (Hrsg.): Handbook of Formal Languages, Vol.1 : Word, Language, Grammar, Springer 1997.
Term.
- Termersetzung
- Termination und Konfluenz
- Vervollst�ndigung (Knuth-Bendix completion)
- Auswertungsstrategien
- Zusatzquelle:
  1. JW. Klop: Term Rewriting Systems (Band 2, Kapitel 1, im Handbuch f�r Logic in Computer Science.)
Graph
- Graphen, Morphismen und Graphoperationen
- Modellierung von W�rtern und B�umen als Graphen
- Graphtransformation mit Verkleben
- Termination und Konfluenz
- Kritische Paare und Vervollst�ndung
- Parsieren
- Attributierung
- Graphvariablen
- Zusatzquellen:
  1. Frank Drewes, Annegret Habel, Hans-J�rg Kreowski: Hyperedge Replacement Graph Grammars [DHK97] (n�tzlicher Hintergrund!)
  2. Frank Drewes, Berthold Hoffmann, Dirk Janssens, Mark Minas, Niels Van Eetvelde: Shaped Generic Graph Transformation [DHJMVE08]
  3. Annegret Habel, Hendrik Radke: Expressiveness of graph conditions with variables [HR10]
  4. Berthold Hoffmann: Conditional Adaptive Star Grammars. [Hof10]
  5. Berthold Hoffmann, Mark Minas: Defining Models - Meta Models versus Graph Grammars. [HM10]
  6. Berthold Hoffmann: Shapely Hierarchical Graph Transformation [Hof01] (Hintergrund zu [DHJMVE08].)
  7. Detlef Plump: Computing by Graph Rewriting [Plu99a] (relevante Kapitel wurden verteilt)
  8. Detlef Plump, Sandra Steinert: Towards Graph Programs for Graph Algorithms [PS04] XS
Schluss
Aufgaben, L�sungen
Literatur

Autor: Dr. Berthold Hoffmann

AG BKB

Zuletzt geändert am: 6. August 2015