Petri Netze

[mad_moses]

Hi,

in der Übung 5 haben wir die verschiedenen Defintionen für Ln-lebendig gegeben. Mir ist aber der Unterschied zwischen L2 und L3 nicht klar.
Wenn es eine Schaltsequenz gibt die für jede natürliche Zahl n mindestens n-mal feuert, dann muss für n-> oo auch oo-mal feuern. Aber wo ist dann der Unterschied zu L3? Wie entscheide ich wann welcher Fall gegeben ist?

Und wie sieht ein beispiel aus für ein L0 lebendiges Petrinetz?

Grüße

[H. Gregor Molter]

Schauen Sie mal in den Jantsch auf Seite 90, Abbildung 2-35. Dort ist ein ganz tolles Petri-Netz bei dem die Transition $t_i$ auch $L_i$-Lebendig ist.
Der Jantsch ist in der INF-Bibliothek im Hauptbestand oder auch per eBook über die ULB einsehbar.

Bzgl. L2 und L3: Ihre Argumentation ist leider falsch.

Es gibt Petri-Netze mit Transitionen die beliebig, aber nur endlich, oft schalten können und Transitionen die unendlich schalten können.
Am Petri-Netz von Jantsch werden Sie sehen, dass die Transition $t_3$ direkt aus dem Initalzustand unendlich oft feuern kann.
Jedesmal wenn $t_3$ feuert wird zusätzlich ein Token in $p_3$ generiert. Die an $p_2$ und $p_3$ angrenzende Transition $t_3$ kann nun für jede Ganzzahl $n$ auch $n$ mal schalten.
Diese Transition kann aber nicht unendlich oft schalten. Damit diese Transition das erste mal schalten kann, muss erst noch $t_1$ schalten und das Token aus $p_0$ wird konsumiert.
Daher kann $t_2$ auch nur endlich oft schalten.

Falls es noch unklar sein sollte bitte einfach kurz bei mir im Büro vorbei schauen. Dann schauen wir gemeinsam über das Jantsch Petri-Netz.

[mad_moses]

Hallo,

nochmal eine Frage: in der MuLö von der Klausur WS08/09 Aufgabe 4b) steht als Antwort, auf die Frage, ob das Petrinetz L1 lebendig ist:"Nein, da der Erreichbarkeitsgraph keinen Zyklus hat ist das Nezt auch nicht L1-lebendig". Wir haben das jetzt aber so verstanden, dass ein Petrinetz L0 lebendig ist, wenn es min. eine Transition gibt, die niemals feuert, bzw. L1-lebendig, wenn jede Transition mindestens einmal feuern kann.



Bei diesem Netz jedoch, hat der Erreichbarkeitsgraph doch auch keinen Zyklus, also L0-lebendig, aber es sollte doch L4-lebendig sein.
Was verstehe ich falsch?

Grüße

[H. Gregor Molter]

Hmm. Woher wissen Sie ob der Erreichbarkeitsgraph keinen Zyklus enthält?

Wenn Sie den Erreichbarkeitsgraph 'einfach' notieren, d.h. die Anzahl der Tokens der Stelle direkt als Zahl in den Zustand notieren, so wird der Erreichbarkeitsgraph unendlich groß. Ich glaube kaum, dass Sie diesen "komplett" gezeichnet haben.

Ansonsten könnte man noch die Tokens der Stellen über eine mathematische Formel ausdrücken. Dann würde man auch erkennen, dass der Erreichbarkeitsgraph einen Zyklus hat. Aufgrund der Kante mit 4 wird der allerdings auch etwas komplizierter und lässt sich jetzt hier nicht einfach in dem Forum per ASCII skizzieren. Betrachten wir doch mal ein leicht einfacheres Netz, wobei die Kante statt mit 4 mit 1 benutzt wird:

Code: Alles auswählen

|        ,---.
|       /     \  /
|  p1  (   +   )----------+
|       \     /  \        |
|        `---'            |
|          |              |   
|          |              |
|         \|/             |
|     +---------+   +-----'---+
| t1  +---------+   +-----,---+   t2
|          |             /|\
|         \|/             |
|        ,-'-.            |
|       /     \           |
|  p2  (       -----------+
|       \     /
|        `---'

Hierzu ist der Erreichbarkeitsgraph:

Code: Alles auswählen

|      ,---.                ,---.
|     /     \   t1       \ /     \
|    ( (1,0) )------------( (0,1) )
|     \     /            / \     /
|      `/|\'    t2          `-.-'
|        +--------------------+

wobei an den Knoten die Anzahl der Tokens annotiert ist mit (#-Tokens in p1, #-Tokens in p2).

Dann erkennt man leicht den Zyklus.

Einfacher geht es aber direkt über die Definition von L1-Lebendigkeit:

"Eine Transition t ist L1-lebendig, falls es mindestens einen erreichbaren Folgezustand gibt in dem t feuern kann."

und

"Ein Petrinetz ist L1-lebendig, falls alle Transitionen L1-lebendig sind".

Schauen wir uns kurz die Transitionen von ihnen an:

Die rechte kann immer dann feuern, wenn in der unteren Stelle ein Token ist.
Die linke kann immer dann feuern, wenn in der oberen Stelle ein Token ist.

Der Initialzustand hat oben ein Token. Wird nun die linke Transition geschaltet, so haben wir oben kein Token mehr, dafür aber unten eines.
Danach kann die rechte Transition geschaltet werden. Nun kann die linke bis zu vier mal feuern (wir haben ja jetzt in der oberen Stelle vier Tokens). Aber egal wie oft (mind. einmal), es wird immer mind. ein Token in der unteren Stelle sein.
Somit kann immer ein erreichbarer Folgezustand "gefunden" werden, in dem erneut die rechte Transition feuern kann.

Dies bedeutet das sowohl die linke als auch rechte Transition L1-lebendig ist. Somit ist auch das Petri-Netz L1-lebendig.

[mad_moses]

also nach unserem Verständnis sollte das Obige PetriNetz L4 Lebendig sein.

Dieses Beispiel sollte doch L1 lebendig sein, da jede Transition einmal feuern kann, der erreichbarkeits graph hat aber keine zyklen, also nach der
Argumentation der alten klausur L0 lebendig, was ist jetzt richtig?



Und danke für die antworten schonmal

grüße

[ChNeumann]

Ich habe mir auch gerade mal die alte Klausur und das Petrinetz mit den Lebendigkeitsbeispielen im Jantsch angeschaut und muss mad_moses zustimmen.

In dem aktuellen simplen Beispiel ist die Transition lebendig im Startzustand (1,0), nicht aber im Folgezustand (0,1).

Per Definition gilt \(x \in R(x)\), also somit auch, dass der Startzustand in der Menge seiner Folgezustände (Erreichbarkeitsmenge) enthalten ist.
Laut Lebendigkeitsdefinition ("L1-lebendig, falls es mindestens einen erreichbaren Folgezustand gibt, in dem t feuern kann") reicht somit schon ein einziger Zustand (auch der Startzustand), der eine Auslösung der Transition erlaubt.

Also muss die Transition L1-lebendig sein.
Da es nur eine Transition gibt und diese L1-lebendig ist, ist das Petrinetz auch L1 lebendig.

Das gleiche wiederum tritt in der alten Klausur auf, in der jede Transition einmal schalten kann, bis man wieder ganz oben ist, aber ein Marker fehlt und man nicht weiter kommt.

[H. Gregor Molter]

also nach unserem Verständnis sollte das Obige PetriNetz L4 Lebendig sein.

Ok. Genau dies meine ich doch auch! Evtl. habe ich das nur nicht ausdrücklich hingeschrieben. Ich dachte sie wollten argumentieren das hier nur L1- oder L-0-Lebendigkeit gilt.

Dieses Beispiel sollte doch L1 lebendig sein, da jede Transition einmal feuern kann, der erreichbarkeits graph hat aber keine zyklen, also nach der
Argumentation der alten klausur L0 lebendig, was ist jetzt richtig?



Und danke für die antworten schonmal

grüße

L1-Lebendigkeit ist hier richtig. In der Tat ist ja die Argumentation in der alten Klausur auch nur auf das dort gegebene Petri-Netz zu verstehen. Wie schon erwähnt, ist diese Klausur auch nicht von mir. Ich hätte wahrscheinlich eher folgendermaßen arumentiert:

Nein, da man an dem Erreichbarkeitsgraph erkennen kann, das in p_6 keine Tokens produziert werden. Daher kann die untere Transition nie feuern und ist somit L0-Lebendig.

Die "Zyklen-Argumentation" ist IMHO auch nur für die Argumentation der L4-Lebendigkeit essentiell.

[H. Gregor Molter]

Also muss die Transition L1-lebendig sein.
Da es nur eine Transition gibt und diese L1-lebendig ist, ist das Petrinetz auch L1 lebendig.

Da stimme ich auch zu. Und ich denke ich habe auch nichts anderes behauptet.

Das gleiche wiederum tritt in der alten Klausur auf, in der jede Transition einmal schalten kann, bis man wieder ganz oben ist, aber ein Marker fehlt und man nicht weiter kommt.

Bitte erklären Sie mir wie in p_6 ein Token zustande kommt und wie Sie die untere Transition schalten können. Das sehe ich in dem gegebenen Petri-Netz leider nicht.

[ChNeumann]

Da stimme ich auch zu. Und ich denke ich habe auch nichts anderes behauptet.

Das diente nur meiner Beweisführung.

Bitte erklären Sie mir wie in p_6 ein Token zustande kommt und wie Sie die untere Transition schalten können. Das sehe ich in dem gegebenen Petri-Netz leider nicht.

Richtig, mein Fehler. Die Kante zwischen p2 und der Transition vor p6 habe ich vollkommen übersehen. Das kommt davon, wenn man die ganze Zeit über Lebendigkeit nachdenkt.

[H. Gregor Molter]

Aber an sich erkennt man hier schon einen der vlt. besten Klausur-Tipps:

Petri-Netz Aufgaben _immer_ als letzte Lösen.