Question

In Graph Game, G/A is states without states in Attractor set,

Attractor =  {s0, s2, s3, s4} ,then in the zielonka exercise answer why it is showing incorrect for the given ans G/A = ({s1,s5,s6,s7};{}), correct ans is shown as G/A= ({s5, s7};{ s1, s6}), which I don't understand, I have solved the question as per exam paper, if states are <=4 then we can directly write source as direct, and in this case states are only 4

Comments

About which exam problem are you talking about? It seems that you have trouble with the first recursive call. That one has to be made for the reduced game, as you write, that much is true. For the rest, it would be necessary to know the particular graph game.

---

Hi,
 I have encountered this question in exercise of VRS which is solved during lecture period, I have uploaded the image now for your reference

Answer 1

Well, in the exam, we allow that students can simply list the correct solution for games that are obtained in the recursive algorithm with no more than 4 nodes. In the exercises, you have more time, and there, we demand all solutions. However, even if you can list a solution without detailed computation, it must be the correct one, of course. 

The game you are referring to is the following one:

In states, s5 and s7, there is only one infinite path with rank 2, so that player 0 wins there for  sure. In state s6, however, player 1 can choose to switch to s1, so that the game consisting of these two states is obtained with highest rank 1. Hence, player 1 wins in states s1 and s6. So, that is the correct solution for the above game.

Comments

Ok, got it, however should the final answer remain same  even if I use states<=4 in exam because if I check that with exercise solution, it differs from the correct answer , this is the answer I get if I follow exam rule ({s1,s5,s6,s7};{s0,s2,s3,s4}), and in exercise its given as ({s5,s7};{s0,s1,s2,s3,s4,s6})