fb18.de
/ Bachelorstudieng
/ PM Formale Informatik
kurze frage
Ist ein "Lineare Vervollstaendigung" eine transitive Huelle oder ist das was ganz anderes?
Ich würd sagen: nein. Eine Ordnungsrelation nennt man ja dann linear, wenn für 2 Elemente a,b entweder a<b, a=b oder b<a gilt. Unter einer linearen Vervollständigung einer Ordnungsrelation würde ich also eine Ordnungsrelation verstehen, die alle bestehenden Beziehungen a<b beibehält, und für vorner unvergleichbare Elemente eine Ordnung definiert.
Also wenn man die relation als graph darstellt und es gibt eine nicht zusammenhaengende komponente, wuerde sie dann bei der transitiven Huelle nicht an den Graph angeschlossen, bei der Linearen vervolstaendigung aber doch? Wonach entscheidet man dann in welche richtung es verbunden sein soll, also wenn man vorher unvergleichbare a und b hatte, soll es a<b oder b<a gelten?
Ich hab ein Beispiel gefunden, wo es dann die transitive Huelle ungleich der Linearen Vervollstaendigun ist, wenn ich das bisjetzt richtig verstanden habe:
a—>b–>c
|\______/
also {(a,b), (b,c), (c, a)}
Wenn man nach linearen Vervollstaendigun fragt, dann ist die Relation schon linear vervollstaendigt, oder?
Und fuer die transitive huelle muss man noch (a,c),(b,a),(c,b) und daswegen auch (a,a), (b,b) und (c,c) dazu nehmen.
Ist das richtig?
Also wenn man die relation als graph darstellt und es gibt eine nicht zusammenhaengende komponente, wuerde sie dann bei der transitiven Huelle nicht an den Graph angeschlossen, bei der Linearen vervolstaendigung aber doch?
Richtig.
Wonach entscheidet man dann in welche richtung es verbunden sein soll, also wenn man vorher unvergleichbare a und b hatte, soll es a<b oder b<a gelten?
Es gibt nicht DIE Linearisierung, beides sind mögliche Linearisierungen.
Wenn man nach linearen Vervollstaendigun fragt, dann ist die Relation schon linear vervollstaendigt, oder?
Das ist keine Striktordnung (nicht OR, wie ich oben fälschlicherweise schrieb), also macht die Frage nach linearer Vervollständigung keinen Sinn.
Ich sitze auch gerade an der Aufgabe.
Gibt es irgendwo eine Definition für die Sternbildung bei der Flussrelation wie sie in Aufgabe 6.4 auftaucht?
Hey Marc,
Gemeint ist mit F* die "transitiv, reflexive Hülle von F".
So, dann stellen ich meine kurze Frage mal hier :)
Was genau ist Beschränktheit eines PT-Netzes?
Laut Definition ist es die maximale Anzahl von Marken in den Plätzen des Netzes.
Die angehängte Grafik zeigt, laut Skript, ein unbeschränktes Netz. Aber ist die maximale Anzahl von Marken in den Stellen nicht "einfach" 1?
Schalt mal immer abwechselnd t2 und t4 - was passiert auf p3?
p3 dürfte dann nie eine Marke bekommen?! Also ich kann mir in t2 ja "aussuchen" wo ich die Marke danach "reinpacke", oder?
Mit Aussuchen ist da nichts. Bei Schaltung von t2 wird eine Marke aus p1 entfernt und je eine Marke in p3 und p4 abgelegt.
Also wird beim abwechselnden Schalten von t2 und t4 die Markenanzahl in p3 immer erhöht (->unendlich) und somit ist der Zustandsraum "unendlich" und nicht beschränkt?!
Genau. Weil der Platz p3 unbeschränkt ist, gilt das auch für das Netz insgesamt.
Ok. Das ist mir jetzt soweit klar geworden, DANKE!!!
Das Netz soll allerdings auch nicht-lebendig sein. Wie komme ich darauf?
Wenn ich vom Anfangszustand t2,t4 und t1 schalte, ist doch t3 auch aktivierbar.
Um Nicht-Lebendigkeit zu zeigen, verwendest du ja auch keine Positiv- sondern Negativbeispiele. Lebendigkeit liegt vor, wenn für alle Transitionen die Lebendigkeits-Invarianzeigenschaft gilt:
[img]
http://latex.codecogs.com/gif.latex?\forall&space;m&space;\in&space;R(S).&space;\exists&space;m%27&space;\in&space;R(N,m).&space;W(\cdot,&space;t)&space;\leq&space;m%27[/img]
Gilt es für
ein t in T nicht, so gilt die Eigenschaft
nicht für alle t in T und somit auch nicht für das Netz (-> Ein Netz ist lebendig, wenn alle Transitionen in der Anfangsmarkierung lebendig sind).
Kannst du jetzt die Nicht-Lebendigkeit erkennen?
Nicht so richtig.
Ich würde jetzt vermuten, dass t3 eine nicht-lebendige Transition ist, weil die Menge der Eingangs-Elemente größer ist als die der Ausgangs-Elemente.
Ich glaube du meinst das Richtige. t3 ist nicht lebendig weil nach Schalten von t1 nichts mehr geht in t3. Zwar ist t3 über eine andere Schaltfolge "potenziell aktivierbar", jedoch eben nicht in jeder erreichbaren Markierung (was genau die Definiton der Lebendigkeit für eine Transition ist: siehe Skript, S.81).
Kurz: Die Markierung (0,1,0,0) ist erreichbar. t3 ist in dieser Markierung aber nicht "potenziell aktivierbar". Somit ist t3 nicht lebendig und damit auch das ganze Netz.
So, dann stellen ich meine kurze Frage mal hier :)
Was genau ist Beschränktheit eines PT-Netzes?
Laut Definition ist es die maximale Anzahl von Marken in den Plätzen des Netzes.
Die angehängte Grafik zeigt, laut Skript, ein unbeschränktes Netz. Aber ist die maximale Anzahl von Marken in den Stellen nicht "einfach" 1?
unabhängig vom vorliegenden Beispiel:
Ein Netz kann bei einer Anfangsmarkierung beschränkt sein aber bei einer anderen vielleicht nicht.
Also kennt man auch noch den Begriff der "strukturellen Beschränktheit", d.h. das Netz ist bei allen im Prinzip möglichen Anfangsmarkierungen beschränkt!
Den ersten Fall, der Beschränktheit bei einer Markierung entscheidet man durch Konstruktion des Überdeckjungsgraphen.
Die strukturelle Beschränktheit kann mit Techniken der linearen Algebra (Kalkulation mit Matrizen und Vektoren) entschieden werden. (Ob das in der Vorlesung erklährt wurde, weiß ich nicht, ich vermute: eher nicht…)
Danke T4Y!
Aber warum ist dann das unten angehängte Netz lebendig?
Wenn ich hier einmal t1 schalte, geht doch in t2 "auch nix mehr".
Schau dir nochmal an, wie Lebendigkeit definiert ist.
Du kannst t1 und danach t3 schalten, dann ist t2 wieder aktiv.
Die Transition muss potentiell (irgendwann in der Zukunft) schaltbar sein, nicht immer und zu jeder Zeit.
Wenn man sich das so überlegt ist es auch logisch, da ja ansonsten so gut wie jedes Netz nicht lebendig wäre, außer es hätte Marken vor jeder Transition liegen.
@Wulf, aber dann kann ich doch auch in meinem ersten Beispiel erst t2, dann t4 und t1 schalten und damit ist auch t3 wieder aktivierbar.
Ich verbuche es einfach unter "nicht verstanden". :)
Stell Dir vor, das ganze ist ein Spiel mit 2 Spielern.
Spieler 1 ist der böse Wulf. Der darf erstmal so lange am Netz rumschalten, wie er will.
Spieler 2 bist Du. Kannst Du - egal was Wulf macht, die Transition t3 wieder zum schalten bringen? (in deinem ersten Netz)
@Wulf, aber dann kann ich doch auch in meinem ersten Beispiel erst t2, dann t4 und t1 schalten und damit ist auch t3 wieder aktivierbar.
Vergleiche doch mal, welche Möglichkeiten dir noch offenstehen, wenn du in beiden Netzen jeweils t1 schaltest.
[28]
Ich glaub du musst dir nochmal ganz genau die Fließtext-Definitionen im unteren Absatz in S.81 durchlesen und wirklich versuchen,
die Begriffe "potenziell aktivierbar" und "erreichbare Markierung" zu durchdringen.
Da scheint aus meiner Sicht das Verständnisproblem zu liegen.
Mit dieser Erklärung komme ich auf jeden Fall weiter, danke!
Also bedeutet "nicht-lebendigkeit", dass ich einen Zustand erreiche, wo das Netz quasi "stoppt".
Schalte ich im ersten Beispiel t1 zuerst, geht nichts mehr. Im zweiten Netz kann ich, egal was/wie geschaltet wird, immer weiter schalten.
Mit dieser Erklärung komme ich auf jeden Fall weiter, danke!
Also bedeutet "nicht-lebendigkeit", dass ich einen Zustand erreiche, wo das Netz quasi "stoppt".
Richtig, bei einer solchen Verklemmung kann keine Lebendigkeit vorliegen. Das ist aber noch nicht hinreichend für ein lebendiges Netz. Wie T4Y schon anregte, ist Seite 81 dein Freund.
Stell Dir vor, das ganze ist ein Spiel mit 2 Spielern.
Spieler 1 ist der böse Wulf. Der darf erstmal so lange am Netz rumschalten, wie er will.
Spieler 2 bist Du. Kannst Du - egal was Wulf macht, die Transition t3 wieder zum schalten bringen? (in deinem ersten Netz)
Wenn ich böse bin, brauche ich mich ja auch nicht an die Regeln halten.
/me malt alle Marken grün an und läuft kichernd davon.