Graphersetzungssystem

Graphersetzungssysteme dienen der formalen Beschreibung der Veränderung von Graphen. Sie werden häufig mit Computerprogrammen implementiert und damit ausführ- und anwendbar gemacht. Ein Graphersetzungssystem ist eine Menge von Graphersetzungsregeln . Eine Graphersetzungsregel besteht aus dem Mustergraphen der linken Seite sowie dem Ersetzungsgraphen der rechten Seite. Eine Regel wird in einer direkten Ableitung angewandt, ist der Arbeitsgraph vor der Regelanwendung, der modifizierte Arbeitsgraph danach.Eine Regelanwendung besteht aus dem Finden einer Instanz von in (Pattern Matching, hier: Teilgraphen-Isomorphie) und dem Ersetzen der gefundenen Instanz durch eine Instanz der rechten Seite .Eine Ableitung ist eine Folge von Regelanwendungen, die einen Ausgangsgraph in einen resultierenden Graphen überführt. Verschiebt sich der Fokus vom Verändern eines gegebenen Graphen hin zum Erzeugen aller, aus einem Startgraphen ableitbarer Graphen, wird von einer Graphgrammatik anstelle eines Graphersetzungssystems und von Produktionen anstelle von Regeln gesprochen. Die Vereinigung der beim systematischen Aufzählen entstehenden Graphen ist die Sprache der Graphgrammatik. Meist werden zudem die Graphelemente in Nichtterminale und Terminale unterschieden, und nur die Nichtterminale ersetzt; unter der Sprache werden dann nur die ableitbaren terminalen Graphen verstanden. Wohlgeformtheit von Graphen wird häufig über das Enthaltensein in der Sprache einer kontextfreien Graphgrammatik definiert. Ein gegebener Graph kann dann mit einem Graphparser, der berechnet, ob er in der Sprache der Graphgrammatik enthalten ist, auf Wohlgeformtheit geprüft werden, im Erfolgsfall erhält man zudem seine Ableitung(en). Graphersetzungssysteme können (auch) als eine Verallgemeinerung der Termersetzungssysteme von (Grund-)Termen / deren Bäumen auf Graphen angesehen werden.