# Zielonka Algorithm

How the attractors of , B= attr1(win'1) = attr1({s0,s2,s3)} are found ? Is it like taking individual terms then find the infinite path then combine them? I did not understand this part, but I understood about how to find the attractors of Qh. Could you please help on this?

+1 vote

To compute the attractor of player 1 of {s0,s2,s3}, we consider the predecessor states of the states, and check whether they belong to the attractor:

Predecessors of s0 are s2 and s4, and since s2 is controlled by player 1, it belongs to the attractor. State s4 belongs to player 0, and player 0 may choose the transition from  s4 to s1, so s4 does not belong to the attractor.

Predecessors of s2 are s3 and s7, and since s3 has only this transition to s2, it belongs to the attractor. State s7 belongs to player 0, so it also belong to the attractor.

The only predecessors of s3 is s0 which belongs to player 0, so it also belong to the attractor.

Hence, we now already have states {s0,s2,s3,s7}. We consider the predecessors of s7 which are s5 and s6 which both belong to player 0. State s5 has however only that transition so it is added to the attractor, but s6 has another transition to s1, so it does not belong to the attractor.

We next consider the predecessors of s5 which s2 and s7 which already belong to the attractor, so we got {s0,s2,s3,s5,s7}.
by (166k points)
selected by
Thank you professor, i understood it