Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For a unique infinite play $p$ in a 2-Player game $G=(V_0,V_1,E)$. Let

$$ \inf(p) \subseteq V_0 \cup V_1 $$

be the set of vertices which occur infinitly often in $p$.

Generlized Büchi (GB) Games are infinite games with a certain winning condition. Let $\mathcal{B} = \{B_1, \dots , B_k\}$ with $B_i \subset V$. Player $0$ wins the GB-game play $p$ iff for each $i$

$$ B_i \cap \inf(p) \neq \emptyset.$$

Which means that in each of the $B_i$ sets at least one vertex occurs infinitly often in the game.

Muller games are more general. The winning condition consists of a set $\mathcal{F_0} \subseteq \mathcal{P}(V)$ and Player $0$ wins a play $p$ iff

$$\inf(p) \in \mathcal{F}_0.$$

Muller games closed under superset are Muller games such that $\mathcal{F}_0$ is closed under supersets:

$$ X \in \mathcal{F}_0, X \subseteq Y \Rightarrow Y \in \mathcal{F}_0.$$

The taks now is to prove that GB-games and Muller games closed under superset are the same winning conditions.

One direction is easy. Just show that $\mathcal{F}_0 := \{X \subset V \mid \forall 1 \leq i \leq k, X \cap B_i \neq \emptyset\}$ is closed under supersets.

The other direction is a little bit more tricky:

Show that for each muller condition closed under supersets there is a GB condition with the same $\inf$-set for each game. E.g. :

$$ V=\{1,2,3,4\} ~~ \mathcal{F}_0=\{\{1,2\},\{3,4\},\{1,2,3,4\}\}$$

The muller condition is closed under supersets. Now the GB-Condition

$$\{\{1,3\},\{2,4\}, \dots$$

Here is where I'm stuck. How do I prevent $\inf(p)=\{1,4\}$ or $\inf(p)=\{2,3\}$? There is no construction for "forbidden combinations". Any ideas?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

For the other direction, let $S$ be the set of all $\it{minimal}$ (without proper subset) set of sets in $\mathcal{F}_0$ in Muller condition, i.e, let $$ S = \{X \subset \mathcal{F}_0 \mid \forall Y \in \mathcal{F}_0, Y \not \subset X \} $$

In your example, $S = \{ \{1, 2\}, \{3, 4\}\}$.

Now consider the cross product of all elements of $S$. Claim is that this cross product forms the corresponding GB-condition. In your example,

$$ S_\times = \{1, 2\} \times \{3, 4\} = \{ \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}\}$$

forms the accepting condition of the GB-game. There are two things to be proved:

  1. Every winning play $p$ of GB-game is also winning in Muller game. This is true because every state in $inf(p)$ comes from at least one state in $S$ in Muller game. Thus, $inf(p) \subseteq \cup_{X \in S} X$. The proof follows from the fact that Muller game is closed under subset.
  2. Every winning play $p$ of Muller game is also winning in GB-game. In this case, let $inf(p) = R \in \mathcal{F}_0$ be the winning set. Since Muller game is closed under superset, there exists a $\it{minimal}$ set $X$ such that $X \subseteq R$. Now at least one element of $X$ appears in any winning condition of the GB-game. Hence, $R \cap \beta \neq \emptyset$, proving the other direction as well.
share|improve this answer
1  
One more thing, the complete superset-closed-Muller condition for your example looks like this $$\{ \{1, 2\}, \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 3, 4\} \}$$ –  Sudeep Jun 25 '13 at 17:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.