Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
lat:homework [2009/11/27 22:51] barbara.jobstmann |
lat:homework [2009/11/27 22:51] barbara.jobstmann |
||
---|---|---|---|
Line 10: | Line 10: | ||
===== 06.11.2009 ===== | ===== 06.11.2009 ===== | ||
- Given a reachability game (G,F), give an algorithm that computes the 0-Attractor(F) set in time O(|E|). | - Given a reachability game (G,F), give an algorithm that computes the 0-Attractor(F) set in time O(|E|). | ||
- | - Consider the game graph shown in below and the following winning conditions: a) Occ(ρ) ∩ {1} ≠ ∅ and b) Occ(ρ) ⊆ {1,2,3,4,5,6} and c) Inf(ρ) ∩ {4,5} ≠ ∅. Compute the winning regions and corresponding winning strategies showing the intermediate steps (i.e., the Attractor and Recurrence sets) of the computation. | + | - Consider the game graph shown in below and the following winning conditions: a) Occ(ρ) ∩ {1} ≠ ∅ and b) Occ(ρ) ⊆ {1,2,3,4,5,6} and c) Inf(ρ) ∩ {4,5} ≠ ∅. Compute the winning regions and corresponding winning strategies showing the intermediate steps (i.e., the Attractor and Recurrence sets) of the computation.\\ {{hw1.gif|Figure 1}} |
- Given a game graph G=(S,S<sub>0</sub>,T) and a set F ⊆ S. Let W<sub>0</sub> and W_1 be the winning regions of Player 0 and Player 1, respectively, in the Buchi game (G,F). Prove or disprove: | - Given a game graph G=(S,S<sub>0</sub>,T) and a set F ⊆ S. Let W<sub>0</sub> and W_1 be the winning regions of Player 0 and Player 1, respectively, in the Buchi game (G,F). Prove or disprove: | ||
- The winning set of Player 0 in the safety game for (G,W<sub>0</sub>) is W<sub>0</sub>, | - The winning set of Player 0 in the safety game for (G,W<sub>0</sub>) is W<sub>0</sub>, | ||
Line 16: | Line 16: | ||
- the winning set of Player 1 in the guaranty game for (G,W_1) is W_1, and | - the winning set of Player 1 in the guaranty game for (G,W_1) is W_1, and | ||
- if f_1 is a winning strategy for Player 1 in the guaranty game for (G,W<sub>0</sub>), then f_1 is a winning strategy in the Buchi game (G,F). | - if f_1 is a winning strategy for Player 1 in the guaranty game for (G,W<sub>0</sub>), then f_1 is a winning strategy in the Buchi game (G,F). | ||
- | |||
- | {{hw1.gif|Figure 1}} | ||
===== 13.11.2009 ===== | ===== 13.11.2009 ===== |