Algorithmus zum nichtdeterministischen Matching in rekonfigurierbaren Petrinetzen

Abstract

Bei der Modellierung und der Simulation des Verhaltens dynamischer Systeme müssen neben ihrem Ablauf auch die Veränderungen am System im Modell abgebildet werden. Daher bestehen rekonfigurierbare Petrinetze aus einem dekorierten Petrinetz und einer Menge von Regeln, die das Petrinetz bei Bedarf flexibel anpassen. Vor einer Regelanwendung wird zuerst das zu transformierende Teilnetz bestimmt. Der dabei zu findende Match muss sowohl die Anforderungen aus der Sicht der Regelanwendung als auch der Simulation erfüllen. Um die Suche effizient zu gestalten, wird in dieser Arbeit ein Algorithmus zum nichtdeterministischen Matching in rekonfigurierbaren Petrinetzen vorgestellt. Die bei einer Graphtransformation einzuhaltenden Klebebedingungen und negativen Anwendungsbedingungen werden direkt in den Matchingprozess einbezogen. Durch seinen nichtdeterministischen Ablauf sorgt er außerdem dafür, dass bei einer Simulation in jedem Transformationsschritt ein unterschiedlicher Match gefunden werden kann. Die Wahrscheinlichkeit der einzelnen Matches hängt dabei von der Struktur der Petrinetze ab. Abschließend werden die Implementierung des Algorithmus in dem Modellierungswerkzeug ReConNet und die daraus resultierenden Konsequenzen beschrieben.

When modelling and simulating the behaviour of dynamic systems it is important to represent their workflow and the system changes in the model. To that effect, reconfigurable Petri nets consist of a decorated Petri net and a set of rules which can flexibly modify the Petri net if required. Before a rule is applied, the transforming subnet must be determined first. The resulting match must meet all requirements of the rule application as well as the simulation. To make this search efficient, an algorithm is presented for the nondeterministic matching in reconfigurable Petri nets. Gluing conditions and negative application conditions which must be met during graph transformation are directly included in the matching process. Through its nondeterminism it also ensures that during simulation a different match can be found in every transformation step. The probability of an individual match is dependent on the structure of the Petri nets. Finally, the implementation of the algorithm in the modelling tool ReConNet and the resulting consequences are described.