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: 1. Februar 2011