Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
lat:homework [2009/11/27 22:45] barbara.jobstmann |
lat:homework [2009/12/06 12:32] radu.iosif |
||
---|---|---|---|
Line 2: | Line 2: | ||
====== LAT Homework ====== | ====== LAT Homework ====== | ||
- | - 02.10.2009: Consider the automata construction from proof of the Myhill-Nerode theorem for a language L. Prove that: | + | ===== 02.10.2009 ===== |
- | * (a) the constructed automaton A is the minimal automaton (in the number of states) that recognizes L; | + | |
- | * (b) any minimal automaton recognizing L is isomorphic to A. | + | Consider the automata construction from proof of the Myhill-Nerode theorem for a language L. Prove |
- | - 06.11.2009: | + | * (a) the constructed automaton A is the minimal automaton (in the number of states) that recognizes L; |
+ | * (b) any minimal automaton recognizing L is isomorphic to A. | ||
+ | |||
+ | |||
+ | ===== 06.11.2009 ===== | ||
- Given a reachability game (G,F), give an algorithm that computes the 0-Attractor(F) set in time O(|E|). | - Given a reachability game (G,F), give an algorithm that computes the 0-Attractor(F) set in time O(|E|). | ||
- | - Consider the game graph shown in below and the following winning conditions: a) Occ(ρ) ∩ {1} ≠ ∅ and b) Occ(ρ) ⊆ {1,2,3,4,5,6} and c) Inf(ρ) ∩ {4,5} ≠ ∅. Compute the winning regions and corresponding winning strategies showing the intermediate steps (i.e., the Attractor and Recurrence sets) of the computation. | + | - Consider the game graph shown in below and the following winning conditions: a) Occ(ρ) ∩ {1} ≠ ∅ and b) Occ(ρ) ⊆ {1,2,3,4,5,6} and c) Inf(ρ) ∩ {4,5} ≠ ∅. Compute the winning regions and corresponding winning strategies showing the intermediate steps (i.e., the Attractor and Recurrence sets) of the computation.\\ {{hw1.gif|Figure 1}} |
- Given a game graph G=(S,S<sub>0</sub>,T) and a set F ⊆ S. Let W<sub>0</sub> and W_1 be the winning regions of Player 0 and Player 1, respectively, in the Buchi game (G,F). Prove or disprove: | - Given a game graph G=(S,S<sub>0</sub>,T) and a set F ⊆ S. Let W<sub>0</sub> and W_1 be the winning regions of Player 0 and Player 1, respectively, in the Buchi game (G,F). Prove or disprove: | ||
- The winning set of Player 0 in the safety game for (G,W<sub>0</sub>) is W<sub>0</sub>, | - The winning set of Player 0 in the safety game for (G,W<sub>0</sub>) is W<sub>0</sub>, | ||
- If f<sub>0</sub> is a winning strategy for Player 0 in the safety game for (G,W<sub>0</sub>), then f<sub>0</sub> is also a winning strategy for Player 0 in the Buchi game for (G,F), | - If f<sub>0</sub> is a winning strategy for Player 0 in the safety game for (G,W<sub>0</sub>), then f<sub>0</sub> is also a winning strategy for Player 0 in the Buchi game for (G,F), | ||
- the winning set of Player 1 in the guaranty game for (G,W_1) is W_1, and | - the winning set of Player 1 in the guaranty game for (G,W_1) is W_1, and | ||
- | - if f_1 is a winning strategy for Player 1 in the guaranty game for (G,W<sub>0</sub>), then f_1 is a winning strategy in the Buchi game (G,F). {{hw1.gif|Figure 1}} | + | - if f_1 is a winning strategy for Player 1 in the guaranty game for (G,W<sub>0</sub>), then f_1 is a winning strategy in the Buchi game (G,F). |
- | - 13.11.2009: | + | |
+ | ===== 13.11.2009 ===== | ||
- Consider the game graph shown below. Let the winning condition for Player 0 be Occ(ρ)={1,2,3,4,5,6,7} | - Consider the game graph shown below. Let the winning condition for Player 0 be Occ(ρ)={1,2,3,4,5,6,7} | ||
- Find the winning region for Player 0 and describe a winning strategy | - Find the winning region for Player 0 and describe a winning strategy | ||
Line 19: | Line 26: | ||
- Compute the winning regions and the corresponding positional winning strategies for Player 0 and 1 in the weak-parity game shown below. {{hw2.gif|Figure 3}} | - Compute the winning regions and the corresponding positional winning strategies for Player 0 and 1 in the weak-parity game shown below. {{hw2.gif|Figure 3}} | ||
- A winning strategy is called "uniform" if it is a winning strategy from every winning state in the game. Let (G,p) be a weak parity game and let W<sub>0</sub> be the winning region of Player 0. For all s ∈ W<sub>0</sub> let f_s be a positional winning strategy from s for Player 0. Construct a uniform winning strategy f from the strategies f_s meaning that for every s ∈ W<sub>0</sub> there is a t ∈ W<sub>0</sub>, s.t. f(s) = f_t(s). | - A winning strategy is called "uniform" if it is a winning strategy from every winning state in the game. Let (G,p) be a weak parity game and let W<sub>0</sub> be the winning region of Player 0. For all s ∈ W<sub>0</sub> let f_s be a positional winning strategy from s for Player 0. Construct a uniform winning strategy f from the strategies f_s meaning that for every s ∈ W<sub>0</sub> there is a t ∈ W<sub>0</sub>, s.t. f(s) = f_t(s). | ||
- | - 27.11.2009: | + | |
- | - Consider the game graph below and the Muller condition F={{2,4,5,7},{1,2,3,4,5,6,7}}. Find an automaton winning strategy for Player 0 in the Muller game with as few states as possible and show that any other automaton strategy with less states is not winning for Player 0. {{hw4.gif}} | + | ===== 27.11.2009 ===== |
- | - Consider the game shown on page 6 of {{slide10.pdf}}. We propose the following "latest appearance queue" (LAQ) strategy for Player 0, initializing the queue with s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>s<sub>4</sub>, (1) add the current state at the front of the LAQ and delete the last state (2) move to the state t<sub>i</sub> whose number i is the number of different states in the current LAQ, e.g., for the sequence of states s<sub>1</sub>, s<sub>3</sub>, s<sub>3</sub>, s<sub>4</sub>, s<sub>1</sub>,... we obtain the following sequence of LAQs: s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>s<sub>4</sub>, s<sub>1</sub>s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>, s<sub>3</sub>s<sub>1</sub>s<sub>1</sub>s<sub>2</sub>, s<sub>3</sub>s<sub>3</sub>s<sub>1</sub>s<sub>1</sub>, s<sub>4</sub>s<sub>3</sub>s<sub>3</sub>s<sub>1</sub>,s<sub>1</sub>s<sub>4</sub>s<sub>3</sub>s<sub>3</sub>,... Decide wheater the new LAQ strategy is a winning strategy for Player 0. Prove this or give a counter-example. | + | |
+ | - Consider the game graph below and the Muller condition F={{2,4,5,7},{1,2,3,4,5,6,7}}. Find an automaton winning strategy for Player 0 in the Muller game with as few states as possible and show that any other automaton strategy with less states is not winning for Player 0.\\ {{hw4.gif}} | ||
+ | - Consider the game shown on page 6 of {{:slide10.pdf}}. We propose the following "latest appearance queue" (LAQ) strategy for Player 0, initializing the queue with s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>s<sub>4</sub>, | ||
+ | - add the current state at the front of the LAQ and delete the last state | ||
+ | - move to the state t<sub>i</sub> whose number i is the number of different states in the current LAQ,\\ e.g., for the sequence of states s<sub>1</sub>, s<sub>3</sub>, s<sub>3</sub>, s<sub>4</sub>, s<sub>1</sub>,... we obtain the following sequence of LAQs: s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>s<sub>4</sub>, s<sub>1</sub>s<sub>1</sub>s<sub>2</sub>s<sub>3</sub>, s<sub>3</sub>s<sub>1</sub>s<sub>1</sub>s<sub>2</sub>, s<sub>3</sub>s<sub>3</sub>s<sub>1</sub>s<sub>1</sub>, s<sub>4</sub>s<sub>3</sub>s<sub>3</sub>s<sub>1</sub>,s<sub>1</sub>s<sub>4</sub>s<sub>3</sub>s<sub>3</sub>,...\\ Decide wheater the new LAQ strategy is a winning strategy for Player 0. Prove this or give a counter-example. | ||
- Let A=(S,s<sub>0</sub>,T,p) be a parity automaton with p:S -> {1,..,k}. Construct a Streett automaton B=(S,s<sub>0</sub>,T,F) equivalent to A that has the same transition structure as A. (i.e., find a suitable set of Streett pairs (F_i,E_i)) | - Let A=(S,s<sub>0</sub>,T,p) be a parity automaton with p:S -> {1,..,k}. Construct a Streett automaton B=(S,s<sub>0</sub>,T,F) equivalent to A that has the same transition structure as A. (i.e., find a suitable set of Streett pairs (F_i,E_i)) | ||
+ | ===== 6.12.2009 ===== | ||
+ | - Exam-like problems on automata and Presburger Arithmetic {{homework.pdf}} |