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

557 users

0 votes

This (image attached) question given in https://es.cs.rptu.de/teaching/vrs/examples/ParityGames1/RandomParityGames.pdf, why is state S1 being included in Attractor 1(S4) in game 0? And why is S1 again included in Attractor 1(S4) in game 4?(in the second image). From understanding S1 state can never go to S4 state. 

 

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

1 Answer

0 votes
In graph games, a player will lose the game if that player cannot choose a transition, hence all players must avoid that their deadend states are reached. Conversely, of course, they try to reach a deadend state controlled by the other player.

In parity games, the winner of an infinite game play is determined in that we determine the highest rank that occurs infinitely often on the game play, and check whether this rank is even or odd. If the game play is finite, the player controlling the final deadend state loses.

When computing an attractor, we compute the fixpoint attrA(φ) :⇔ μx.(φ ∨ ⟨A⟩x)  with ⟨A⟩φ := A ∧ <>φ ∨ B ∧ []φ. Since it is a least fixpoint, we start the fixpoint computation with false, and obtain next φ ∨ ⟨A⟩false = φ ∨ ⟨A⟩false = φ ∨ A ∧ <>false ∨ B ∧ []false = φ ∨ B ∧ deadend, i.e., the φ-states plus the deadend states of the other player.

Somehow, the deadend states may considered to be wrong in this set since from there, it is not possible to enforce a visit of Qh. However, their membership in the attractor is justified in that reaching them also makes player A win as well as reaching the states with the highest rank (infinitely often).
by (170k points)
why is state S1 being included in Attractor 1(S4) in game 0?
As written above, player 1 aims at reaching a state in Qh={s4} since player 1 will win if that is infinitely often possible (which will be decided later). Even stronger is the wish to reach a deadend state of player 0, since all states that allow this are directly winning states of player 1, since player 0 will lose there. Hence, the attractor set is actually the set of states where player 1 can enforce reaching either  Qh or deadend states of the other player. If you read my answer above, it explains that the fixpoint definition of the attractor exactly computes this and this is okay.
Got it.
Shouldn't state S6 in game 1 also be an attractor1 (qh) and state S6 controlled by player 0 goes to the deadend state? Or S6 will try to send it to S2 to avoid reaching the dead end state and hence, it is not included?
I am not sure what you mean. Do you consider the subgame listed in section 4.5 of the mentioned pdf? If so, I don't understand your question, since in that game G1, the highest rank is 6, thus even, so that we compute the attractor of player 0 of the set {s6}. Therefore, s6 is already included in the attractor.
Sorry, I was referring to Game 0. Shouldn't S6 be in the attractor1(Qh) in Game 0 as S6 goes to a deadend?
No, S6 does not belong to the attractor, since S6 is controlled by player 0, and player 0 can choose to move to states S2 or S5, so that S6 may not be necessarily reached. Computing attractor sets is more difficult than computing the states that can reach Qh. You have to check for the predecessors which player controls them, and depending on this, it may be sufficient that there is one transition to Qh, or it may be required that all transitions go to Qh.
Understood. Thanks
Imprint | Privacy Policy
...