💡 OCR-Versionen können vom Original abweichen 💡

§1. HISTORISCHES, MOTIVATION

Petri-Netze (konzipiert 1962 durch C. A. Petri [21]) liefern ein sehr komfortables und mittlerweile kaum wegzudenkendes Hilfsmittel bei der Darstellung und Analyse verschiedenartiger Vorgänge. Insbesondere die systemanalytischen Aspekte im Zusammenhang mit interaktiv ablaufenden Prozessen, wie z. B. Synchronisation (locking), Systemstillstand (deadlock), Objektverfügbarkeit (scheduling) können in einer sehr anschaulichen Form angegangen werden [5], [12]. Die zu den Petri-Netzen äquivalenten algebraischen Aggregate, wie Vektor-Additions- bzw. Ersetzungssysteme¹ erleichtern zudem die rechnergestützte Simulation von derartigen Interaktionen.

Die naturgemäß schwierigen systemanalytischen Probleme, wie z. B. Aspekte der Lebendigkeit eines vorliegenden Systems [7], [14], werden in Anlehnung an das Petri-Netz-Modell zwar anschaulicher, aber selbstverständlich nicht leichter. So sind beispielsweise Fragen im Zusammenhang mit den Erreichbarkeitsmengen² von Petri-Netzen häufig gar nicht algorithmisch entscheidbar – und wenn, dann meistens extrem komplex. Andere wiederum konnten bislang weder als entscheidbar noch als unentscheidbar ausgewiesen werden.

Andererseits sollte nicht übersehen werden, dass die in [21] vorgestellten Gebilde, die wir im weiteren als „gewöhnliche Petri-Netze“ bezeichnen wollen, nicht uneingeschränkt universell sind. An die Grenzen deren Anwendbarkeit stößt man z. B. beim Simulieren von Berechnungsvorgängen. Die durch Rabin konzipierte schwache Berechenbarkeit durch ein (gewöhnliches) Petri-Netz (angelehnt an das WPNC-Modell³), gilt nur für eine bestimmte Klasse von Funktionen. Zwar sind sogar einige stark wachsende Funktionen in diesem Sinne berechenbar (z. B. die Ackermann-Funktion – [18]), aber bereits bei relativ simplen, nicht monoton wachsenden Funktionen entsteht die Notwendigkeit, das Feuern von Transitionen an das Leersein von bestimmten Stellen zu knüpfen. Das so modifizierte Petri-Netz enthält sog. inhibitor-Kanten und ist nur eine der inzwischen zahlreichen Varianten des Grundmodells. Andere enthalten z. B. Stellen mit eingeschränkten Aufnahmekapazitäten oder verzweigte Kanten – um nur einige zu nennen [27]. Diese Modifikationen machen aber die o. e. Probleme, z. B. das Erreichbarkeitsproblem, offensichtlich nicht leichter, denn die WPNC-Berechenbarkeit von hinreichend komplizierten Funktionen (z. B. notwendigerweise auf der Basis von Petri-Netzen mit inhibitor-Kanten) ist gleichbedeutend mit entsprechend diffizilen Erreichbarkeitsmengen, mit allen Konsequenzen für die damit zusammenhängenden Probleme. So modifizierte Petri-Netze sind demnach zwar leistungsfähiger, können aber die an sie angelehnte Systemanalyse erheblich erschweren oder gar unmöglich machen.

Diesen Sachverhalt beobachten wir anhand des sog. allgemeinen Erreichbarkeitsproblems⁴. Die Frage, ob ein gewisser Zustand von einem fixierten Anfangszustand aus erreicht werden kann, ist von essentieller Bedeutung für viele systemanalytische Aspekte (z. B. Erreichbarkeit eines Zustandes, der dem Systemstillstand entspricht [5] oder Systemlebendigkeit⁵ [14], [29]), sowie für viele Probleme aus dem Bereich der Algebra und Numerik. Dieses Problem ist entscheidbar, bezogen auf die gewöhnlichen Petri-Netze – unentscheidbar hingegen für Petri-Netze mit inhibitor-Kanten⁶ [7].

Interessant ist aber auch die Frage, wie schwer das Erreichbarkeitsproblem ist und wie es praktisch gelöst werden kann (hier denken wir stets an gewöhnliche Petri-Netze). Die naheliegende Vorgehensweise, dieses Problem durch Bestimmung der Erreichbarkeitsmenge zu lösen, ist überraschenderweise algorithmisch nicht realisierbar. Unentscheidbar ist auch die Frage der mengentheoretischen Inklusion bzw. Gleichheit von Erreichbarkeitsmengen zweier Petri-Netze (sog. Inklusions- bzw. Gleichheitsproblem⁷ [2], [9], [28]). So verwundert es nicht, dass die in [16], [26] vorgestellten Algorithmen keinerlei Aspekte der Erreichbarkeitsmengenbeschreibung angehen. Eine brauchbare Beschreibung der Erreichbarkeitsmengen ist nur bei den gegenüber dem Grundmodell etwas vereinfachten Petri-Netzen möglich [1], [6], [17], [20]. All das zeugt von ziemlicher Nähe zur Grenze des algorithmisch Machbaren, und es kann folglich davon ausgegangen werden, dass das Erreichbarkeitsproblem sehr komplex ist. Selbst bei paralleler Abarbeitung kommt man um exponentielle Laufzeiten nicht herum [15].

Die Unentscheidbarkeit des Inklusionsproblems und die darauf zurückgehenden enormen Schwierigkeiten bei der praktischen Lösung des (allgemeinen) Erreichbarkeitsproblems veranlassen uns zu fragen, unter welchen Umständen die unentscheidbaren Probleme entscheidbar, insbesondere das Erreichbarkeitsproblem einfacher werden kann. Wir haben bereits angedeutet, dass die Erreichbarkeitsmengen von gewissen Klassen der gewöhnlichen Petri-Netze berechnet werden können. Der Preis dafür ist eine gegenüber dem Grundmodell eingeschränkte Leistungsfähigkeit (bisher sprachen wir von leistungssteigernden Varianten des Grundmodells) – diese ist aber in der Praxis häufig ausreichend. Ein wichtiger Spezialfall liegt vor, wenn die Erreichbarkeitsmenge endlich ist, was sogar feststellbar ist [11]. Es ist nämlich in diesem Falle möglich, die Erreichbarkeitsmenge zu berechnen, und folglich ist das (endliche) Inklusionsproblem (und damit auch das Gleichheitsproblem) entscheidbar [11], wenn auch von exorbitanter Komplexität [18]. Auch unendliche Erreichbarkeitsmengen können berechenbar sein – vorausgesetzt, dass deren Struktur hinreichend regulär ist, z. B. semilinear, d. h. erfassbar durch die sog. Presburger-Arithmetik [22]. (Die Semilinearität der Erreichbarkeitsmenge ist ebenfalls algorithmisch feststellbar.)

Derartige Resultate können – neben der Vereinfachung vieler Probleme – auch eine andere Rolle spielen. Noch vor wenigen Jahren waren sie Teillösungen des damals noch offenen Erreichbarkeitsproblems und Meilensteine auf dem Wege zu dessen endgültigen Lösung. Gerade dieser Umstand war das Hauptmotiv für die Entstehung dieser Arbeit. Das bislang offene Erreichbarkeitsproblem von Petri-Netzen mit genau einer und dessen Unentscheidbarkeit bei mehreren inhibitor-Kanten haben uns veranlasst, nach ähnlichen Resultaten zu suchen. Insbesondere konzentrieren wir uns in der vorliegenden Arbeit auf die Frage, inwieweit die auf der Semilinearität basierenden Aussagen auf Petri-Netze mit inhibitor-Kanten übertragbar sind.

Die Semilinearität der Erreichbarkeitsmengen ist zunächst bei Petri-Netzen von geringer Dimension⁸ zu erwarten. Diese Vermutung bestätigte Van Leeuwen [25] für (gewöhnliche) Vektor-Additionssysteme der Dimension n ≤ 3, gefolgt von Hopcroft und Pansiot [10], die sogar die exakte, dimensionsbezogene Grenze der Semilinearität ermittelten von (n ≤ 5). In der vorliegenden Arbeit wird u. a. untersucht, ob inhibitor-Kanten diese Grenze tangieren. Unabhängig von der Dimension sind die Erreichbarkeitsmengen von sog. selbstdualen Petri-Netzen stets semilinear [4]. Das Erreichbarkeitsproblem ist in diesem Falle äquivalent zum Wortproblem kommutativer Halbgruppen⁹ [4], [8], und folglich ist dessen Komplexität von besonderem Interesse für uns [19].

Des Weiteren werden einige ergänzende Aussagen über die Struktur der Erreichbarkeitsmengen von gewöhnlichen Vektor-Ersetzungssystemen gemacht. Die hier ermittelte dimensionsbezogene Semilinearitätsgrenze gibt zugleich Aufschluss über das Kompaktierungspotential kontrollierender Stellen, die ein Bestandteil von Vektor-Ersetzungssystemen, nicht aber Vektor-Additionssystemen sind. Die Auswirkung solcher Stellen auf die dimensionsbezogene Semilinearitätsgrenze gewöhnlicher Petri-Netze wird damit ebenfalls geklärt. Die Kombination: kontrollierende Stellen und inhibitor-Kanten ist in diesem Zusammenhang etwas diffiziler und wird in der vorliegenden Arbeit nur im Sinne von oberen Schranken geklärt (ein möglicher Weg zur Beantwortung relevanter Fragen hinsichtlich dieser Konstellation wird durch eine entsprechend untermauerte These mit weiteren Hinweisen aufgezeichnet). Außerdem diskutieren wir Vektor-Additionssysteme, bei denen das Feuern von Transitionen zusätzlich an das Vorliegen eines bestimmten Zustandes geknüpft ist. Diese Gebilde sind leistungsfähiger und besitzen eine Semilinearitätsgrenze von n ≤ 2 [10]. Sog. Vektor-Ersetzungssysteme mit kontrollierenden Zuständen werden definiert und deren Semilinearitätsgrenze ermittelt. Auch hier wird die Auswirkung von inhibitor-Kanten auf diese Grenze untersucht, was uns ein Resultat liefert, das in Anbetracht der Minsky-Barsdin-Theoreme [30] zwar vermutet, jedoch nicht hergeleitet werden konnte.

Abschließend diskutieren wir einige offene Fragen, z. B. das Erreichbarkeitsproblem der Petri-Netze mit genau einer inhibitor-Kante. Ein interessanter Spezialfall geht auf schwach-monotone inhibitor-Transitionen zurück. Die Rückführung auf die Erreichbarkeitsmengen gewöhnlicher Petri-Netze ist wegen der Unentscheidbarkeit des Inklusionsproblems zwar noch nicht die abschließende Lösung des Erreichbarkeitsproblems, kann aber sicherlich als ein guter Tipp auf dem Wege dahin angesehen werden.

Die vorliegende Arbeit vermittelt Denkanstöße hinsichtlich vielerlei offener Probleme, z. B. hinsichtlich der Projektionen der Petri-Netz-Erreichbarkeitsmengen auf Stellen, um nur ein weiteres, bislang ungelöstes Problem zu nennen. Diese Projektionen sind bei gewöhnlichen Vektor-Additionssystemen unabhängig von der Dimension semilinear [3] – es ist allerdings unklar, wie viele inhibitor-Kanten diesen Sachverhalt verändern können.

______________________________

1. 1. 1. engl. vector addition system, vector replacement system.
      2. diese entsprechen den Mengen aller erreichbaren Systemzustände.
      3. engl. weak Petri net Computer. Es handelt sich dabei um ganzzahlige Funktionen [16], [25].
      4. engl. general reachability problem.
      5. engl. liveness problem.
      6. bei zwei und mehr inhibitor-Kanten besteht Äquivalenz zum Halteproblem.
      7. engl. inclusion problem, equality problem.
      8. gemeint ist die Anzahl der Stellen.
      9. engl. word problem for commutative semigroups.