Projekt: Algorithmen zur Analyse von Petrinetzeigenschaften

Durée: seit Mai 1990

Mots clés: Petrinetze, Invarianten, Komplexität

But:

Es werden Methoden untersucht, Algorithmen zur Berechnung von Invarianten in speziellen High-Level-Netzen auch auf allgemeinere Netzklassen anwenden zu können.Eines der wichtigsten Instrumente zur Analyse von S/T-Netzen ist die Berechnung/Verifikation von Invarianten. Um diese auch für höhere Netzklassen zu finden, ist man dagegen i.a. noch auf seine eigene Intuition angewiesen. Die Invariantenberechnung ist erst für einige stark eingeschränkte Unterklassen der höheren Netze möglich, mit denen größere Systeme aber nicht sinnvoll modelliert werden können.Das Ziel der Untersuchung ist es daher, Algorithmen zu finden, um Invarianten auch für ausdrucksstarke, in der Praxis einsetzbare Netzklassen berechnen zu können.Von besonderem Interesse sind hierbei die Funktionsklassen, aus denen die Kanteninschriften der Netze gewonnen werden. Kann für jede dieser Funktionen ein sogenanntes generalisiertes Semiinverses gefunden werden, so ist eine Erweiterung des Gauß-Algorithmus anwendbar, die durch Lösung eines linearen Gleichungssystems über den Funktionen die Invarianten berechnet.Die Kanteninschriften werden im allgemeinen als Ausdrücke (Terme oder Polynome) über einigen Grundfunktionen dargestellt. Die Relationen zwischen den Funktionen werden als Gleichungen angegeben, und man rechnet in dem durch diese Gleichungen definierten Quotientenring.Sind die Grundfunktionen so gewählt, daß die Reihenfolge ihrer Anwendungen das Ergebnis nicht beeinflußt, so findet man sich in der Klasse der kommutativen Polynome wieder. Hier gibt einem die Theorie der Gröbner-Basen mächtige Instrumente an die Hand, die u.a. auch die Berechnung der oben angegebenen Semiinversen ermöglichen.Ein Hauptziel der weiteren Arbeit besteht darin, diese Algorithmen auf nichtkommutative Polynome und eventuell auf allgemeine Terme zu erweitern.