Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes
In slide 159, I can see the attr0(Qh) = {s7}. Why is not {s0,..,s7}

In slide 160, attr1(Qh) = {s4}. Why it is not {s1,...,s5} or {s0,...,s5}

In slide 161, attr0(Qh)= {s0,s1,s5,s6}. Because S1:16 has the highest rank and lets player 0 wins?

Please help me with my understanding
in # Study-Organisation (Master) by (850 points)

1 Answer

0 votes

attr0{Q) is the set of states where player 0 can enforce that a state in Q is reached, no matter what player 1 will do in the states controlled by player 1. The game graph you are discussing looks as follows:

attr0({s7}) = {s7} since for all other states, player 1 can select the transition s6->s5 to avoid that s7 will be reached. Note that all states except for s7 can only reach s7 by first visiting s6, but there the control is given to player 1, and player 1 may select the transition s6->s5. Hence, player 0 can only enforce reaching s7 when we are already in s7. 

The game graph on page 160 looks as follows:

Here, attr1({s4}) = {s4} since we can reach s4 only from state s3 which is controlled by player 0. Player 0 may choose there however the transition s3->s2, so that s4 would not be reached. Hence, player 1 can only enforce reaching s4 when we are already in s4. 

On slide 161 (see above), attr0({s1}) = {s0,s1,s5,s6} since states s2 and s3 cannot reach s1 at all, and therefore, player 0 cannot enforce reaching s1 from there. However, player 0 can enforce this from the other states which are therefore in the attractor set.

by (170k points)

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy
...