Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
lat:homework [2009/11/27 22:52] barbara.jobstmann |
lat:homework [2009/11/27 22:54] barbara.jobstmann |
||
---|---|---|---|
Line 26: | Line 26: | ||
===== 27.11.2009 ===== | ===== 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}} | - 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>, (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 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)) | ||