Was sind Petri-Netze von welcher Bedeutung sind sie fürs transObjects®?

3. Mai 1997   / Rainer A. StawarzMeta, Whitepaper

Dieser Artikel ist outdated.

Kapitel 1:

Die stark proprietäre und daher generell nur in der Special-Build-Edition erhältliche transObjects®-Anwendung processPRO widmet sich der Analyse, Auswertung, Kontrolle und Optimierung innerbetrieblicher Vorgänge im Kontext der Dislokation und Umwandlung von Ressourcen und das über den klassischen Kern des Enterprise Resource Planing hinaus. Eine solche Verallgemeinerung einer ERP-Lösung gehört zu den schwierigsten Aufgabenbereichen, die von der Anwendungssoftware überhaupt zu bewältigen sind. Die Anlehnung an ein probates systemanalytisches Mittel in der Gestalt von Petri-Netzen war seinerzeit eine der wichtigsten Weichenstellungen für das heutige transObjects® processPRO. Der nachfolgende Artikel soll die grundlegenden Konzepte rund um Petri-Netze vor dem Hintergrund deren wissenschaftlicher Erforschung vorstellen und gleichzeitig ansatzweise eine Überleitung zu den im transObjects® processPRO angewandten Gebilden geben.

Stellen wir uns vor, wir beobachten in einer Montagehalle für Verbrennungsmotoren den folgenden Sachverhalt: An einer der dort zahlreich vorhandenen Montagestellen werden Zylinderblöcke aus je zwei gleichen Hälften zusammen geschraubt, wofür jeweils 6 Schrauben benötigt werden. Stünden wir vor der Aufgabe, diesen Vorgang im Kontext der involvierten Ressourcen – d.h. des Verbrauchs der beiden Zylinderblockhälften und der Schrauben sowie des Ausstoßes des zusammen geschraubten Zylinderblocks – grafisch darzustellen, so würden wir wohl in etwa so etwas zeichnen, wie die nachfolgende Abb. 1 a) zeigt.

Bildhaft gesprochen, fließen die Ressourcen aus den Input-Stellen – etwa aus Vorratsbehältern – in die Montage hinein und werden auf der Outputseite als Bestandteil einer anderen Ressource, hier des Zylinderblocks, ausgestoßen. Klar, diese Ressource könnte wiederum eine Input-Ressource für einen weiteren Prozess sein, etwa da, wo man diese mit Kolben, Kurbelwellen etc. bestückt.

Würden wir darüber hinaus der Tatsache Rechnung tragen wollen, dass unsere Montage nur mit Hilfe eines speziellen Schraubenschlüssels erfolgen kann, der alle Schrauben gleichzeitig hineindreht, würden wir unsere Zeichnung wohl um eine weitere Ressource ergänzen, deren Vorhandensein zwar für die Montage selbst unerlässlich ist, also zwingend gebraucht, jedoch infolge dieser nicht verbraucht wird. Unsere Abb. 1 a) bekäme somit eine Modifikation, wie auf der obigen Abb. 1 b) zu sehen ist. Auch hier fließt die betreffende Ressource in die Montage hinein, wird aber anschließend nicht auf der

Outputseite mit ausgestossen, sondern vielmehr an die ursprüngliche Input-Stelle in völlig unveränderter Form zurückgeschickt. Diese Ressource ist wieder uneingeschränkt für den betreffenden Prozess bzw. auch für andere, die sie evtl. benötigen könnten, verfügbar – lässt man etwa Verschleissprozesse etc. ausser Betracht.

Wenn wir das alles so gemacht haben, würden wir nicht schlecht staunen, wenn man uns erzählte, wir hätten nichts Geringeres entworfen, als ein sog. Petri-Netz für den hier betrachteten Vorgang! In der Tat, Petri-Netze sind ein Mittel bei einer – nennen wir es – ressourcenabhängigen Prozessanalyse, das nicht nur sehr anschaulich, sondern auch absolut nahe liegend ist; der Urheber und Namensgeber Carl Adam Petri möge uns diesen Einwurf nachsehen.

Betrachten wir nachfolgend noch einige Petri-Netze aus [RAS], so könnten wir versuchen, diese graphentechnisch zu erfassen, denn Graphen sind diese Gebilde allemal, offensichtlich mit gerichteten und beschrifteten Kanten sowie zweierlei Knoten. Während die einen für so etwas wie die Orte für bestimmte Ressourcen (Schrauben, Zylinderblockhälften etc.) stehen, tun es die anderen für die Prozesse selbst, die eine Verarbeitung dieser Ressourcen (deren Gebrauch, Verbrauch, Ausstoß etc.) darstellen. So nennt man auch die ersten der beiden (die runden Knoten) einfach „Stellen“, während die dunkelgrünen Balken mit dem Originalbegriff aus dem Englischen bedacht sind: wir nennen sie „Transitionen“.

Der graphentechnischen Erfassung entzogen sich bislang die schwarzen Punkte, die in den Stellen placiert sind (Abb. 2). Die Belegung der Stellen mit den sog. Token ist jedoch für die Struktur des Petri-Netzes irrelevant. Allenfalls wird dadurch der Zustand des Petri-Netzes zu einem x-beliebigen Zeitpunkt dargestellt, genauer gesagt, die Quantitäten einzelner Ressourcen zu diesem Zeitpunkt. Wie sich diese infolge der Montage ändert, schildern die beiden „vorher/nachher“-Zustände aus Abb. 2 a/b) – dazu später mehr.

An dieser Stelle – weil es sich so aufdrängt – wollen wir einen scheinbaren Widerspruch auflösen, in dem der Name processPRO zu dem FAQ-Artikel http://www.ks-informatik.de/faq.php?id=13 steht, aber wie gesagt nur scheinbar. Bei der Erklärung des Wesens von objektorientierter Sicht der Dinge wird nämlich vom Ansetzen an den Prozessen selbst abgeraten und zwar zugunsten von den weitaus weniger volatilen Rahmenbedingungen, unter denen diese ablaufen. Auf der anderen Seite hat aber processPRO eben diese Prozesse zum Gegenstand. Was gilt also nun?

Schöner könnte die praktische Anlehnung an die objektorientierte Sicht der Dinge nicht demonstriert werden, als eben anhand von Petri-Netzen. Die Analyse der Abläufe im processPRO ist in der Tat an Graphen angelehnt, in denen ja die Stellen für Objektklassen, die Token für die Objekte selbst und Transitionen für Klassenmethoden stehen! Diese Analyse ist also strikt objektorientiert und gilt eben den wenig volatilen Klassenstrukturen, d.h. den Rahmenbedingungen, unter denen die Prozesse ablaufen.

Aber nun zurück zu unseren schwarzen Token. Der Begriff des Zustandes eines Petri-Netzes zu einem x-beliebigen Zeitpunkt hat sich uns bereits vorher aufgedrängt. In der Tat wird eine momentane Verteilung der Token (also der Ressourcen in einem zu analysierenden System) mit dem Zustand des gegebenen Petri-Netzes identifiziert und auch so bezeichnet. Wie die Abb. 2 darlegt, kann sich dieser Zustand ändern, indem ein Prozess stattfindet, der die Ressourcen in einer vordefinierten Form umwandelt – hier werden Schrauben und Zylinderblockhälften verbraucht und ein vorgefertigter Zylinderblock hervorgebracht. Diesen Prozess bezeichnen wir in der PN-Terminologie als die „Zustandsüberführung“, die infolge vom „Feuern einer Transition“ stattfindet.

Nach dem ersten Touch mit den Petri-Netzen ist man vielleicht ein wenig geneigt, eine Parallelität zu elektrischen Schaltkreisen zu sehen, was jedoch gänzlich unangebracht ist. Denn während im elektrischen Schaltkreis ein Schaltvorgang, z.B. das Schliessen eines Relais, zwingend erfolgen muss, sobald eine bestimmte Spannung anliegt, haben wir im Falle von Petri-Netzen diesen Determinismus nicht. Vielmehr fragen wir danach, was in einem Petri-Netz alles passieren kann. Insofern galt die Aufmerksamkeit der Wissenschaftler seit jeher den sog. Erreichbarkeitsmengen und auch das transObjects® processPRO stellt auf diese Fragestellungen ab, wie wir nachfolgend sehen werden.

Für die Bedürfnisse des vorliegenden Artikels reicht das intuitive Verständnis von Petri-Netzen, gestützt auf die oben angeführten Beispiele, gerade mal aus. Dennoch seien nicht nur mathematische Puristen auf den FAQ-Artikel http://www.ks-informatik.de/faq.php?id=32 verwiesen, der die von Petri-Netzen aufgeworfenen Fragestellungen vor dem Hintergrund deren wissenschaftlicher Erforschung etwas formeller fasst und so das Verständnis der Funktionsweise von transObjects® processPRO vertieft. Für die nun überfällige graphentheoretische bzw. algebraische Formalisierung der Petri-Netze möge der interessierte Leser die reichlich zitierte Fachliteratur zu Rate ziehen. Vorliegend, wohl wissend um die abschreckende Wirkung einer mathematischen Formel J, wollen wir es mit folgender Beschreibung versuchen: Wir identifizieren Petri-Netze als einen Graphen bestehend aus Stellen und Transitionen sowie einer Kantenabbildung von Stellen zu Transitionen und umgekehrt, mit jeweils ganzzahliger Beschriftung (auch Kantenvielfachheit genannt). Kanten mit der Vielfachheit gleich Null werden als nicht existent angesehen.

Apropos „was alles passieren kann“. Natürlich gilt unser Interesse denjenigen Zuständen, die irgendwie problematisch sind. Es kann sich z.B. um einen Deadlock handeln, d.h. einen mangels Ressourcen verursachten Systemstillstand, oder um einen Blowup, d.h. um eine unkontrollierte Zunahme von Ressourcen innerhalb eines Systems – um vorerst nur diese beiden zu nennen. Welchen volkswirtschaftlichen Wert es beispielsweise hätte beantworten zu können, ob es in einem AKW zu einer unkontrollierten Zunahme an Neutronen kommen kann oder nicht, braucht man wohl nicht zu erläutern. Auf der anderen Seite wissen wir, dass solche Systeme viel zu komplex sind, als dass wir in absehbarer Zukunft adäquate Petri-Netze hierfür zu erwarten hätten.

Die processPRO-Analysen gelten jedoch weitaus weniger komplexen Systemen und auch nur einigen relevanten Klassen, Ressourcen und Methoden. Dennoch leisten diese Analysen eine wertvolle Hilfestellung bei der Optimierung von betriebswirtschaftlich relevanten Prozessen, sie sind unerlässlich für ein modernes und erfolgreiches Management. Denn es wäre schlicht unverantwortlich, mögliche Deadlocks, Blowups, Nebenläufigkeiten etc. nicht abzustellen. Und um das tun zu können, muss man zuerst wissen, dass es diese potentiell im System gibt und wo sie lauern, bevor man es zu einem ziemlich hohen Preis empirisch in Erfahrung bringt.

Warum dann transObjects® processPRO und nicht etwas anderes, was z.B. unter der Überschrift „Workflow-Analyse“ etc. Ähnliches verspricht? Die K&S GmbH steckte das gesamte profunde Wissen deren Entwickler in das processPRO. Gleichzeitig ist das Objektorientierte an transObjects® wie geschaffen für diese Aufgabe. Die Kombination aus Sachkompetenz und passender Technologie spricht also deutlich fürs transObjects® processPRO.

Abb. 1 a) Abb 1 b)

Kapitel 2

Im Kapitel 1 des FAQ-Artikels über Petri-Netze und deren Anwendung in der transObjects®-Technologie haben wir ansatzweise die Komplexität der Problematik, wie sie durch diese Gebilde aufgeworfen wird (und der sich die transObjects®-Applikation processPRO stellt), kennen gelernt. Vorliegend wollen wir unsere Überlegungen vertiefen, indem wir Petri-Netze etwas formeller fassen und die Problematik, die sie aufwerfen – insbesondere diejenige rund um die Erreichbarkeitsmengen – genauer ergründen; Letzteres nicht zuletzt vor dem Hintergrund der Geschichte deren wissenschaftlicher Erforschung.

Eine der recht häufig gestellten Fragen zu unseren Artikeln über processPRO und Petri-Netze(eigentlich sollten unsere Artikel Fragen klären anstatt welche aufwerfen J) lautet, wozu sich über die per se unendlichen Erreichbarkeitsmengen Gedanken machen, wenn doch alles in der realen Welt beschränkt ist? Nun, so einfach ist es nicht. Zum einen können z.B. Datenbankkapazitäten, betrachtet in einem konkreten systemanalytischen Kontext, sehr wohl praktisch unbeschränkt sein. Zum anderen erhoffen wir uns von den theoretischen Erkenntnissen ein besseres Gespür z.B. für die Komplexität bestimmter Aufgaben, wie Sie in Gebilden à la Petri-Netz naturgemäss steckt.

Im ersten Teil unserer Überlegungen haben wir eine graphentechnische Erfassung von Petri-Netzen unter Meidung jeglicher mathematischer Formeln 😉 vorgelegt. Wörtlich heisst es in Teil 1: „Wir identifizieren Petri-Netze als Graphen, bestehend aus Stellen und Transitionen sowie einer Kantenabbildung von Stellen zu Transitionen und umgekehrt, mit jeweils ganzzahliger Beschriftung (auch „Kantenvielfachheit“ genannt). Kanten mit der Vielfachheit gleich Null werden als nicht existent angesehen“.
Etwas formeller gesprochen – aber immer noch unter Meidung jeglicher mathematischer Formeln J – bilden gewöhnliche Petri-Netze (d.h. ohne sog. inhibitor-Kanten) ein Tupel (S,T,k) bestehend aus den beiden Knotenmengen sowie der Kantenabbildung k, wobei es sich bei S und T stets um endliche und zueinander disjunkte Mengen handelt und die Kantenabbildung wie gesagt die Quantität (also Vielfachheit) der gerichteten Kanten (inklusive Null) zwischen jeweils heterogenen Knoten angibt.

Aber Graphen hin oder her – aus guten Gründen wollen wir vorliegend eine andere Fassade von Petri-Netzen beleuchten. Betrachten wir hierzu die nachfolgend aufgeführten Abbildungen, die eine sukzessive Zustandsüberführung in einem Petri-Netz infolge vom Feuern bestimmter Transitionen darlegen. Identifizieren wir die Stellen mit Achsen eines n-dimensionalen Raumes und deren Belegung mit der Quantifizierung derselben, also dem Koordinaten, so stellen wir fest, das die augenblicklichen Zustände eines Petri-Netzes den Punkten in einem n–dimensionalen ganzzahligen Raum (Gitter) entsprechen und das Feuern einer Transition einem Übergang (Translation) von einem Gitterpunkt zu einem anderen entspricht!

Der so modifizierte Begriff der Transition, der diese nicht nur als einen Graphenknoten beschreibt, sondern darüber hinaus die Kanten, in die sie involviert ist, mit einschliesst, gestattet nun das Feuern einer Transition als eine Translation in dem n-dimensionalen Gitter aufzufassen, demnach als eine simple Vektoraddition x+t, wobei t nun einen Translationsvektor darstellt und T all solche Vektoren in einem gegebenen Petri-Netz enthält.

So gesehen verwundert es nicht allzu sehr, dass man in der Fachliteratur über Petri-Netze mit Begriffen wie Vectorsets, Multisets, (VAS)/(VRS)’s (vector addition/replacement system) etc. häufig konfrontiert wird. Denn in der Tat sind solche Gebilde die rein algebraische Form von Petri-Netzen, wie sie sowohl in den theoretischen Überlegungen wie auch in der IT selbst weitaus mehr Anwendung findet, als die noch so anschauliche aber wenig praktikable Urform der „place / transition“ – Graphen. (Für den Äquivalenzbeweis sowie die Unterscheidung zwischen (VAS)’s und (VRS)’s möge der Leser einmal mehr [RAS] konsultieren).
Nun aber erinnern wir uns wieder an die wohl wichtigste Frage, die Petri-Netze aufwerfen, und die sich auch uns zuvor aufgedrängt hat, nämlich die, was alles (in einem zu analysierenden System) passieren kann. Wörtlich genommen ist es doch nichts anderes als die Frage nach allen Zuständen, die ein Petri-Netz von einem vordefinierten Anfangszustand ausgehend annehmen kann. Anders ausgedrückt ist es die Menge aller Punkte x, die durch eine regelkonforme Kombination von Transitionsverktoren erreicht werden kann; so nennen wir diese Mengen auch „Erreichbarkeitsmengen“.

Das alles scheint auf den ersten Blick wie auf dem Silbertablett geliefert (und mit mathematischen Formeln untermauert „scheint“ es noch mehr J). Ein Vektorsystem, wo die Addition als einzige Operation auftritt? Hat das nicht etwas mit [MPR], der Presburger Arithmetik, zu tun? Demnach müsste doch jede Erreichbarkeitsmenge durch die Menge aller Linearkombinationen von den Translationsvektoren zu beschreiben sein (und wäre somit stets linear!). Zwar hätten wir noch zu berücksichtigen, dass nicht jede Translation zulässig ist – insbesondere nicht in den halbnegativen Raum, da es keine negativen Quantitäten an den Stellen geben kann (die Transitionen bei Ressourcenmangel nicht feuern dürfen) – aber das war es schon, so scheint es.

Aber leider… weit gefehlt! Welche Konsequenzen es hat, Translationen und demzufolge auch die Erreichbarkeitsmengen unter den Vorbehalt der Zulässigkeit (Schaltbarkeit von Transitionen) zu stellen, wurde relativ früh deutlich und zwar durch Rabin’s Beweis von der algorithmischen Nicht-Berechenbarkeit von Erreichbarkeitsmengen gewöhnlicher Petri-Netze!

Diese Erkenntnis ist für jemanden, der bislang nur über unsere Sparte Bekanntschaft mit Petri-Netzen gemacht hat, erstaunlich – sind doch die Erreichbarkeitsmengen bei den bislang vorgestellten Beispielen zumeist endlich und auch sonst können sie fast immer intuitiv bestimmt werden. Und dennoch gibt es keinen Algorithmus, keine allgemeingültige Struktur von Erreichbarkeitsmengen, die deren einheitliche Charakterisierung ermöglichen würde. Das sog. Erreichbarkeitsmengenproblem bei den gewöhnlichen Petri-Netzen ist unentscheidbar, d.h. diese sind nicht algorithmisch berechenbar (Grundzüge der Berechenbarkeitstheorie möge der Leser der Fachliteratur entnehmen).

Wer sich bis dahin der Tragweite der zuvor erwähnten „kleinen Einschränkung“ der ungehemmten Presburger Arithmetik nicht bewusst war, ist es jetzt wohl endgültig. Denn die unscheinbare Vorbehaltstellung des Feuerns von Transitionen – nennen wir es eine Inhibition – hievt in der Tat die Komplexität des im Falle der ungehemmten Vektorsystems trivialen Erreichbarkeitsmengenproblems jenseits des algorithmisch Machbaren!

Und wie gering wirklich diese Inhibition ist, wird einem spätestens nach dem Studium von [HPA] und [RAS] deutlich. Denn in der Tat mag auf den ersten Blick eine Inhibition, die auf eine kontrollierende Stelle zurückgeht, nicht unbeträchtlich erscheinen. Eine Stelle, die eine Input- und Outputstelle zugleich für eine Transition ist, bedeutet doch, dass es mit dem Verbot der halbnegativen Räume (d.h. mit mindestens einer negativen Koordinate) nicht getan ist.

Dennoch zeigten Hopcroft und Pansiot in [HPA], dass kontrollierende Stellen (vgl. Abb. 1b),2a),2b)) stets durch 3 zusätzliche nicht-kontrollierende Stellen simuliert werden können, so dass die Erreichbarkeitsmengen im Sinne der Projektion auf die ursprünglichen Stellen unverändert bleiben (zahlreiche Beispiele für diese Simulation findet der Leser in [RAS], eine Ausdehnung auf Petri-Netze mit sog. inhibitor-Kanten enthält das Lemma 3.3 mit nachfolgenden Korollaren).

Die Konsequenz aus diesem Lemma ist für uns eben die, dass die Inhibition in gewöhnlichen Petri-Netzen wirklich auf das Verbot der halbnegativen Räume beschränkt werden kann, was die nicht-Entscheidbarkeit des Erreichbarkeitsmengenproblems nicht weniger erstaunlich macht. Hingegen spielt die obige Transformation im TransObjects® keine entscheidende Rolle. Vielmehr arbeitet processPRO direkt mit kontrollierenden Stellen, also den Vector Replacement Systems (VRS)’s, wie noch zu gegebener Zeit zu sehen sein wird.

Obwohl die Nicht-Berechenbarkeit der Erreichbarkeitsmengen relativ früh feststand und das Gleichheits- bzw. Inklusionsproblem der Erreichbarkeitsmengen hieraus folgernd ebenfalls als unentscheidbar ausgewiesen werden konnten [HGB], vermuteten viele Forscher fortan, dass ein anderes damit sehr verwandtes Problem entscheidbar sein könnte. Es handelt sich um das sog. Erreichbarkeitsproblem, also die Fragestellung, ob ein bestimmter Zustand x von einem festen Anfangszustand aus erreichbar ist (natürlich mittels zulässiger Translationen bzw. Schaltfolgen). Die Grundidee war dabei die, dem Erreichbarkeitsproblem ohne eine implizite Bestimmung der Erreichbarkeitsmenge beizukommen. Es sei vorweggenommen, dass diese unscheinbare Einschränkung bzw. Präzisierung des Erreichbarkeitsmengenproblems uns in der Tat über die Grenze des algorithmisch Machbaren hilft!

Die Entscheidbarkeit des Erreichbarkeitsproblems bedeutet für uns, dass wir zwar die Frage nach dem, was alles passieren kann, nicht direkt beantworten können, aber wenigstens die, ob ein bestimmter Zustand – der in vielerlei Hinsicht problematisch sein kann – vorkommen kann. Das ist zwar schon etwas, kann aber in der Praxis eine unbefriedigende Antwort liefern. Die Frage, der man sich auch in der Vergangenheit widmete, lautete daher, unter welchen Umständen lässt sich eine umfassendere Antwort auf diese Fragen doch geben. Das Augenmerk der Forscher richtete sich nun darauf, ob denn die Inhibition in gewöhnlichen Petri-Netzen zwingend die so elegante Linearität der inhibitionsfreien Vektor-Additionssysteme zerstören muss.

Offensichtlich ist Letzteres nicht immer der Fall. Ein Petri-Netz, das ausschliesslich aus nichtnegativen Transitionen besteht, hat zwangsläufig lineare Erreichbarkeitsmengen und in den bislang zitierten Fällen (Abb. 1, 2) sind diese Mengen sogar endlich und dadurch zwangsläufig zumindest semilinear, also aus endlich vielen linearen Mengen bestehend. Offensichtlich ist das Erreichbarkeitsproblem in solchen Fällen berechenbar, wenn es die Erreichbarkeitsmengen selbst schon sind. So war auch die Semilinearität von Erreichbarkeitsmengen zunächst der Dreh- und Angelpunkt in der Petri-Netz-Forschung. Van Leuwen wandte sich beispielsweise in [JVL] der Vermutung zu, dass ein hinlänglich kleines Petri-Netz (gemeint ist stets die geometrische Dimension des VAS/VRS, d.h. die Anzahl der Stellen) semilineare Erreichbarkeitsmengen haben dürfte. In der Tat konnte er beweisen, dass ein dreidimensionales Petri-Netz stets semilineare Erreichbarkeitsmengen hat, völlig unabhängig von der Anzahl und Art der Transitionen. Im Folgenden haben Hopcroft und Pansiot gezeigt, dass dies sogar auf fünfdimensionale (VAS)’s zutrifft. Eine andere Teillösung lieferte Cardoza in [EWC] für sog. selbstduale Petri-Netze, d.h. mit einer Art Symmetrie. Auch hier konnte gezeigt werden, dass diese Klasse von Petri-Netzen stets semilineare Erreichbarkeitsmengen hat, mit allen Konsequenzen für das Erreichbarkeitsproblem und das Erreichbarkeitsmengenproblem.

Aber bei aller Zufriedenheit mit diesen Teilresultaten, einen Vermutstropfen gab’s dann schon noch. Nehmen wir das Petri-Netz aus [RAS], so stellen wir fest, dass die Semilinearität bereits in relativ kompakten Petri-Netzen nicht unbedingt vorliegen muss, was unsere Teillösungen des Erreichbarkeitsproblems weniger wertvoll erscheinen lässt. Was ist also nun mit dem (allgemeinen) Erreichbarkeitsproblem?

In der Tat erwies sich der Ansatz, dem Erreichbarkeitsproblem ohne eine implizite Errechnung von Erreichbarkeitsmengen beizukommen als goldrichtig. Den als ersten geltenden Beweis für die Entscheidbarkeit des Erreichbarkeitsproblems lieferte Mayr in [EWM] und zwar auf dem klassischen Wege über einen konkreten Algorithmus. Nicht viel später lieferte Kosaraju in [SRK] einen anderen Beweis, wobei viele in seiner Arbeit inzwischen einige „mistakes“ festgestellt haben wollen.

Wie knapp entscheidbar d.h. wie hart das Erreichbarkeitsproblem wirklich ist, zeigt uns nicht zuletzt die Arbeit von Lipton [RLN]. Der exponentielle Speicherplatzbedarf bedeutet, dass ein Algorithmus zur Lösung des Erreichbarkeitsproblems auch dann exponentielle Laufzeiten hätte, wenn wir hierfür Maschinen mit noch so vielen parallel arbeitenden Prozessoren einsetzen würden. Interessanterweise sollte sich erst viele Jahre später herausstellen, dass es ein noch härteres und dennoch entscheidbares Problem durchaus gibt und zwar ist es – um es vorwegzunehmen – das Erreichbarkeitsproblem von Petri-Netzen mit genau einer sog. inhibitor-Kante.

Kapitel 3

Im Kapitel 2 unserer Überlegungen über Petri-Netze und deren Rolle in der transObjects®-Technologie haben wir die Komplexität der Probleme rund um die Erreichbarkeitsmengen durch Nachzeichnen der Geschichte von deren wissenschaftlicher Erforschung beleuchtet. Wir haben den langwierigen Weg der Wissenschaft hin zur Lösung des Erreichbarkeitsproblems kennen gelernt und zwar stets vor dem Hintergrund des als (algorithmisch) unentscheidbar ausgewiesenen Erreichbarkeitsmengenproblems. Im Falle von Petri-Netzen mit den sog. Inhibitor-Kanten, bei denen sich die Geschichte teils wiederholen sollte, haben wir vorliegend Ähnliches vor.

Zu den in der Fachwelt bekanntesten qualitativen Erweiterungen des Grundmodells von Vektor-Additions-Systemen (und somit von gewöhnlichen Petri-Netzen) gehören so genannte Inhibitor-Kanten –nachfolgend „i-Kanten“ genannt; grafisch durch den Unterbruch –| |– dargestellt.

Die qualitative Verschärfung der Inhibition durch die i-Kanten beruht darauf, dass diese – ausschliesslich von einer Stelle zu einer Transition führend – eine Transition nur dann zum Feuern befähigen, wenn die betreffenden (Inhibitor-) Stellen leer sind. Somit wird das Grundprinzip der gewöhnlichen Petri-Netze – nennen wir es positive Inhibition – total auf den Kopf gestellt. Denn während normalerweise das Feuern von Transitionen nur bei Vorhandensein von hinlänglich vielen Ressourcen stattfinden kann, ist dies genau umgekehrt, wenn i-Kanten mit im Spiel sind.

Auf den ersten Blick scheint diese wie auch jede andere Verschärfung der Inhibition – und die daraus zwangsläufig resultierende Verkomplizierung von Strukturen der Erreichbarkeitsmengen – weiter weg von der praxisnahen Anwendung im transObjects® processPRO zu führen. Jedoch bei genauerem Hinschauen stellen wir rasch fest, dass exakt das Gegenteil zutrifft. transObjects® processPRO arbeitet nämlich mit Petri-Netzen, bei denen die Inhibition sogar noch weiter verallgemeinert ist, indem sie von Fall zu Fall für alle Transitionen einzeln redefiniert werden kann („derrived classes“ lassen grüssen!). Deshalb ist ein genaueres Studium von Petri-Netzen mit i-Kanten im Hinblick auf das letztendlich zu beleuchtende Funktionsprinzip von transObjects® processPRO ausserordentlich hilfreich.

Ähnlich wie bei der Erforschung von gewöhnlichen Petri-Netzen, hat auch hier die Fachwelt relativ früh die Grenzen des algorithmisch Machbaren aufgezeigt bekommen. Aus Minsky’s Arbeit [MLM] aber auch aus diversen Abhandlungen von Rabin war nämlich bereits Anfang der 70’er Jahre zu folgern, dass das allgemeine Erreichbarkeitsproblem von Petri-Netzen mit zwei nur zwei i-Kanten unentscheidbar ist. Allerdings konnte diese Erkenntnis nicht auf Petri-Netze mit genau einer i-Kante ausgedehnt werden; das Erreichbarkeitsproblem für diese Gebilde blieb seinerzeit, zu Minsky’s Zeiten, unbeantwortet und das sollte für gut 30 Jahre so bleiben. Angesichts der nachgewiesenen Unentscheidbarkeit des allgemeinen Erreichbarkeitsproblems von Petri-Netzen mit zwei i-Kanten und der bekannten exorbitanten Härte dieses Problems im Falle von gewöhnlichen Petri-Netzen – also ohne i-Kanten – konnte die Nicht-Entscheidbarkeit des Erreichbarkeitsproblems bei exakt einer i-Kante durchaus vermutet werden. Allerdings gab es gleichermassen auch genau anders lautende Mutmassungen. So untersuchte beispielsweise Rainer A. Stawarz 1991 in [RAS] den Einfluss von i-Kanten auf die Struktur von Petri-Netz-Erreichbarkeitsmengen, insbesondere hinsichtlich deren Semilinearität, und stellte – gewissermassen auf den Spuren von van Leuwen, Hopcroft und Pansiot – fest, dass der Einfluss von nur einer i-Kante auf die dimensionsbezogenen Semilinearitätsgrenzen marginal ist und dass erst eine zweite i-Kante eine signifikante Verschiebung nach sich zieht. Auch das qualitative Enhancement von so genannten WPNC-Computern (Weak Petri-Net Computer) hielt sich demnach im Falle von nur einer i-Kante in Grenzen, während zwei oder mehr eine völlig andere Qualität darstelltenDennoch – mehr als eine Vermutung war es nicht. Denn auch eine einzige i-Kante verschärft offensichtlich die Inhibition der gewöhnlichen Petri-Netze, was die Struktur der betreffenden Erreichbarkeitsmengen ganz bestimmt nicht vereinfacht. Das Erreichbarkeitsproblem von Petri-Netzen mit genau einer i-Kante blieb auch in [RAS] offen und es sollte noch gute 10 Jahre halten, genau bis Anfang 2004, als Klaus Rheinhard in [KLR] einen Beweis für eben diese Vermutung lieferte.

Der Beweis von Klaus Rheinhard ist eine Folgerung aus einer sehr umfassenden Untersuchung von Petri-Netzen mit i-Kanten und deren Erreichbarkeitsmengen. So lernen wir aus [KLR], dass die i-Kanten in einer bestimmten Anordnung zueinander liegen müssen, damit das Erreichbarkeitsproblem unentscheidbar wird (sog. nested transitions). Zwangsläufig ist ein solches Konstrukt mit nur einer i-Kante nicht möglich, woraus, quasi als Beifang, die Bestätigung für die bis dato vermutete Entscheidbarkeit der betreffenden Fragestellung folgt.

Eine weitaus weniger umfassende Untersuchung, jedoch mit einer gezielten Beweisführung für die Entscheidbarkeit des allgemeinen Erreichbarkeitsproblems von Petri-Netzen mit genau einer i-Kante, findet der interessierte Leser demnächst im Nachtrag zu [RAS] auf unserer Website.

Literaturverzeichnis:

[ARK] T. Araki, T. Kasami, Decidable Problems on the Strong Connectivity of Petri Net Reachability Sets, Theoret. Comp. Sci. 4 (1977) 99-119;

[BLM] H.K. Büning, T. Lettmann, E.W. Mayr, Projections of Vector Addition System Reachability Sets Are Semilinear, Report No. STAN-CS-88-1199, Stanford, California (1988);

[CAP] C.A. Petri, Kommunikation mit Automaten, Institut für Instrumentelle Mathematik, Bonn, Schriften des IMM Nr. 2, (1962).

[DCO] D.C. Open, A Upper Bound on the Complexity of Presburger Arithmetic, J. Comput. Systems Sci., 16 (1978) 323-332.

[EWC] E.W. Cardoza, Computational Complexity of the Word Problem for Commutative Semigroups, MAC Technical Memorandum 67, M.I.T. (1975).

[EWM] An Algorithm for the General Petri Net Reachability Problem, Proc. 13th Ann. ACM STOC, 1981, Milwaukee, WI, 238-246.

[EWM] E.W. Mayr, An Algorithm for the General Petri Net Reachability Problem, SIAM J. Comput. 13,3 (1984) 441-460.

[EWM] E.W. Mayr, Persistence of Vector Replacement Systems is Decidable, Acta Informatica, 15 (1981) 309-318.

[FCO] F. Commoner, Deadlocks in Petri Nets, Applied Data Research, Wakefield MA, CA 7206-3211 (1972), Applied Data Research Inc.

[HGB] H.G. Baker, Rabin’s Proof of the Undecidability of the Reachability Set Inclusion Problem of Vector Addition Systems, MIT Project MAC, CSGM 79, Cambridge, Mass. (1973).

[HPA] J. Hopcroft, J.J. Pansiot, On the Reachability Problem for 5-Dimensional Vector Addition Systems, Theoret. Comp. Sci., 8 (1979) 135-159;

[JGR] J. Grabowski, The Decidability of Persistence for Vector Addition Systems, IPL, 11 (1980) 20-23;

[JVL] J. Van Leeuwen, A Partial Solution to the Reachability Problem for Vector Addition Systems, Sixth Ann. ACM Symp. on the Theory of Computing (1974) 303-309.

[KLR] K. Reinhardt Counting as Method, Model and Task in Theoretical Computer Science, Uni Tübingen, Habilitationskolloquium 16.02.2005, Kapitel V.

[KLT] K. Lautenbach, Exakte Bedingungen der Lebendigkeit für eine Klasse von Petri-Netzen, GMD Bonn (St. Augustin), Bericht Nr. 82, (1973).

[MLM] M. L. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall, 1971.

[MH0] M. Hack, Decidability Questions for Petri Nets, MIT, LCS, TR 161, Cambridge, Mass., (1976).

[MH1] M. Hack, Petri Nets and Commutative Semigroups, MIT Project MAC, CSGN 18, Cambridge, Mass. (1974).

[MH2] M. Hack, The Equality Problem for Vector Additon Systems is Undecidable, C.S.G. Memo 121. Project MAC, M.I.T. (1975).

[MM1] E.W. Mayr, A.R. Meyer, The Complexity of the Finite Containment Problem for Petri Nets, Journal of the Association for Computing Machinery, Vol 28, No. 1 (1981) 561-576.

[MM2] E.W. Mayr, A.R. Meyer, The Complexity of the Word Problems for Commutative Semigroups and Polynomial Ideals, Advances in Mathematics 46,3 (1982), 305-329.

[HM] H. Müller, Decidability of Reachability in Persistent Vector Replacement Systems, Proc. 9th Symposium on MFCS (1980), LNCS 88, Springer, New York, 426-438.

[MPR] M. Presburger, Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, Compute-Rendus du I. Congrés des Mathématiciens des pays, Warsaw (1930) 92-101.

[RAS] R.A. Stawarz, Über Petri-Netze mit inhibitor-Kanten, deren Leistungsfähigkeit und Erreichbarkeitsmengen, J.W. Goethe-Univ. Frankfurt/M, (1991);

[RKM] R. Karp, R. Miller, Parallel Program Schemata, J. Comp. Syst. Sci. 3 (1969) 147-195;

[RLN] R. Lipton, The Reachability Problem is Exponential-Space Hard, Dept. Computer Science Rep. 62, Yale Univ., New Haven, CT (1976).

[RMK] R.M. Keller, Vector Replacement Systems: a Formalism for Modelling Asynchronous Systems, Princeton Univ., Princeton, NJ, CSL, TR 117, (1972).

[SRK] S.R. Kosaraju, Decidability of Reachability in Vector Addition Systems, Proc. 14th Ann. ACM STOC, (1982) 267-281.

[STY] G. Sacerdote, L. Tenney, The Decidability of the Reachability Problem for Vector Addition Systems, Proc. 9th Ann. ACM Stoc, (1977) 61-76.

[1] Decision Problems for Petri Nets and Vector Addition Systems, MIT Project MAC, MAC-TM 59, Cambridge, Mass. (1975).

[1] Decidability Questions for Petri Nets, MIT, LCS, TR 161, Cambridge, Mass. (1976).

[1] The Recursive Equivalence of the Liveness Problem and the Reachability Problem for Petri Nets and Vector Addition Systems, 15th Annual Symposium on SWAT, New Orleans, LA, (Oct. 1974) 156-164;