Zielonka Algorithm in Exam Aug-2023

Question

I have a doubt about parity game question in the question paper. In exercise we have given a question we will find the highest value and %2 for Attr i and i-1 for the next one. Is that whole process counted as one Game or else how we are calculating Each game?

Secondly, What is meant by source in the question paper?

And in each game we will assume all the states are still there, and what will be the Qh of the Attr formula in corresponding games?

When we are supposed to halt the games?

Thanks in advance.

Answer 1

The Zielonka algorithm solves a parity game recursively by decreasing the size of the considered parity games in each recursive call. The "source" mentioned in the question means (as explained in the text of the exam problem) that you should either list their the number of the recursive call that returns the results that you list there or that you write "direct" in case the problem became so simple that one can see the result directly.

In the recursively constructed games, the states are removed step by step, so that they are no longer there. 

The Zielonka algorithm is precisely described on page 152: