Hi,
ich hätte ne Frage zu den Überdeckungsgraph:
Es handelt sich um Übungsaufgabe 6.5 c):
Wenn ich jetzt den Überdeckungsgraphen anfange zu zeichnen dann komm ich von p1 mit einem a zu (p2 + p3) usw. irgendwann ist man dann bei (p1 + p3) nach dem ausführen von d.

Meine Frage ist: Muss ich jetzt die (w'Px)-Notation schon nach dem ersten Schritt von (p1)-a-> (p2 + p3) verwenden [Also (p1)-a-> (p2 + w'p3)] oder erst nachdem das erste mal die Trans. d ausgeführt wurde ?

Ergänzung: Und wie sieht es mit w'p5 aus? evtl sogar schon gleich (p1)-a-> (p2 + w'p3 + w'p5)

nach dem algorithmus schreibst du erst ein Omega rein, wenn du eine neue Markierung hinzunehmen würdest, aber diese neue Markierung größer ist als eine bisher existierende. Das bezieht sich aber auf die komplette Markierung und nicht nur auf die Markierung einer stelle. Bei (p2 + p3) und (p1 + p3) z. B. ist keine Markierung größer als die andere.
Angenommen es gibt nur diese drei Stellen, dann kannst du die markierung ja als Vektor schreiben. (p2 + p3) = (0,1,1) und (p1 + p3) = (1,0,1). Jetzt vergleichst du die beiden Vektoren komponentenweise.

es gilt aber 1 > 0, 0 < 1, 1 = 1 für die drei Komponenten. Also einmal < und einmal >. Daher gilt weder < noch > für die kompletten Vektoren. Sie sind unvergleichbar.

Insoforn würde in deinem Beispiel überhaupt kein Omega benutzt (bis zu dem Punkt, der von dir beschrieben ist). Aber angenommen du hättest jetzt ein system, bei dem gilt

m0 -a-> m1 -b-> m2 -c-> m3

und m1 wäre (1,0,0) und m3 eigentlich (2,0,0), dann ersetzt du bei m3 die 2 durch das Omega. m1 bleibt aber wie es ist.