FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

FGI 2 - Blatt 10 Überdeckungsgraph

FGI 2 - Blatt 10 Überdeckungsgraph 2008-01-14 14:00
Anonymer User
Moin!
Blatt 10 : http://www.informatik.uni-hamburg.de/TGI/lehre/vl/WS0708/FGI2/sec/fgi2-a10.pdf
Aufgabe 10.1:

Ich habe ein Problem mit dem Algorithmus zur Berechnung des Überdeckungsgraphen (skript S. 201):
Was genau bedeutet m_1-*->m_2 ? Soll es bedeuten, dass ein Weg im (bisher erstellten) Überdeckungsgraphen gibt, der von m_1 nach m_2 führt (in Pfeilrichtung)? Dann bekommt man nämlich ein Problem mit dem Algorithmus: Es wurde dann ja nie eine Kante zu m' eingezeichnet, es sei denn m' existiert zufälligerweise schon im Graphen.
Hoffe, jemand blickt bei meinem Schreibwirrwarr durch.

RE: FGI 2 - Blatt 10 Überdeckungsgraph 2008-01-14 14:11
Anonymer User
ergänzende Frage: bedeutet m1 != m2, dass dies für alle p aus P gilt ? (analog zu m1 <= m2)

RE: FGI 2 - Blatt 10 Überdeckungsgraph 2008-01-14 14:13
Anonymer User
noch eine Frage: ist omega kleiner als omega ? w < w ?

Leider ist Michael Duvignau krank, sonst würde ich ihn mit Fragen löchern…

RE: FGI 2 - Blatt 10 Überdeckungsgraph 2008-01-14 15:36
georg
Was genau bedeutet m_1-*->m_2 ?  Soll es bedeuten, dass ein Weg im (bisher erstellten) Überdeckungsgraphen gibt, der von m_1 nach m_2 führt (in Pfeilrichtung)?

Meines Erachtens ist in dem Algorithmus in 2.2.2 gemeint [latex]\mathbf{m}''\stackrel{*}{\longrightarrow}\mathbf{m}[/latex] statt [latex]\mathbf{m}''\stackrel{*}{\longrightarrow}\mathbf{m'}[/latex].
Dann kann man den Pfeil verstehen als "es gibt einen Weg, der nur Markierungen aus V
besucht". Der Algorithmus dürfte aber auch so funktionieren, wenn mann den Pfeil versteht
als "es dürfen, bis auf [latex]\mathbf{m'}[/latex], nur Markierungen aus V besucht werden".

ergänzende Frage: bedeutet m1 != m2, dass dies für alle p aus P gilt ?  (analog zu m1 <= m2)

Nein, es ist: [latex]\mathbf{m}_1\ne \mathbf{m}_2\Longleftrightarrow \exists p\in P: \mathbf{m}_1(p)\ne \mathbf{m}_2(p).[/latex].

noch eine Frage: ist omega kleiner als omega ?  w < w ?

Nein.

RE: FGI 2 - Blatt 10 Überdeckungsgraph 2008-01-14 17:44
T
noch eine Frage: ist omega kleiner als omega ? w < w ?

Nein.

aber: [latex]\omega + 1 = \omega[/latex] und [latex]\omega - 1 = \omega[/latex]