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

1.2k questions

1.3k answers

1.7k comments

588 users

0 votes


B = Attr i-1 (win i-1) ==> Attr 0 (win 0) ==> {s5}, how is it {s0,s5,s7}?

ago in * TF "Emb. Sys. and Rob." by (120 points)

1 Answer

0 votes

Here is the Zielonka algorithm:

In the example, the player i owning states Qh={s0,s7} with the highest rank h=9 is i=1. Thus, we first compute A := attractor(1,Qh) := {s0,s1,s2,s3,s4,s6,s7}. 

Removing these states from the game just leaves state s5 with a self-loop. It is therefore clear that this game is won by player 0 so that we get as solution of that game winA0={s5}; winA1={}.

Considering the algorithm, we now have to check whether winA_{1-i}=winA0={s5} is empty. Since that is not the case, we have to compute the attractor B := attractor(0,winA0) := attractor(0,{s5}) := {s0,s5,s7}, which is justified as follows: s0 is owned by player 0 and has a transition to s5, and s7 is owned by player 1, but there is only the transition to s5, so that player 1 has to choose that one. The other states are all owned by player 1 and have transitions to other states.

Note that in the algorithm, the indices are sometimes 1-i and not i-1. Maybe you are confused with this, since you mixed that up in your question.

ago by (171k points)

Related questions

0 votes
1 answer
0 votes
1 answer
asked Aug 26, 2023 in * TF "Emb. Sys. and Rob." by farwinr (380 points)
0 votes
1 answer
asked Aug 22, 2023 in # Study-Organisation (Master) by yk (2.7k points)
Imprint | Privacy Policy
...