GAMES logo Nodes: Warsaw
Aachen Bordeaux Edinburgh Paris Rice Uppsala Warsaw Vienna
Warsaw Task 6 Publications Events Vacancies

Task 6: Game models for protocols

Objectives

The main goal is to develop a model of protocols using the theory of multiparty games with incomplete and uncertain inform ation. Games with cooperating players will serve as tools for validating protocols for client-server database systems, more complicated scenarios of games with hostile players, uncertainty and infinite state spaces will be used for analysing cryptographic protocols.

Material

Background literature

[1] M. Jurdzinski, Deciding the winner in parity games is in UP co-UP, Information Processing Letters, vol. 68, no. 3, pp. 119-124, 1998.
[ List ]

@ARTICLE{Jurdzinski98,
  AUTHOR = {Marcin Jurdzi\'{n}ski},
  TITLE = {Deciding the Winner in Parity Games Is in {UP}~{$\cap$}~co-{UP}},
  JOURNAL = {Information Processing Letters},
  VOLUME = {68},
  YEAR = {1998},
  PAGES = {119--124},
  NUMBER = {3},
  URL = {http://www-cad.eecs.berkeley.edu/~mju/Papers/Jur98-IPL.ps}
}

[2] M. Jurdzinski, Small progress measures for solving parity games, in Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, vol. 1770 of Lecture Notes in Computer Science, pp. 290-301, Springer-Verlag, 2000.
[ List ]

@INPROCEEDINGS{Jurdzinski00,
  AUTHOR = {Marcin Jurdzi\'{n}ski},
  TITLE = {Small Progress Measures for Solving Parity Games},
  BOOKTITLE = {Proceedings of the 17th Annual Symposium on 
                   Theoretical Aspects of Computer Science, STACS~2000},
  YEAR = {2000},
  PUBLISHER = {Springer-Verlag},
  PAGES = {290--301},
  SERIES = {Lecture Notes in Computer Science},
  VOLUME = {1770},
  URL = {http://www-cad.eecs.berkeley.edu/~mju/Papers/Jur00-STACS.ps}
}

[3] C. Stirling, Local model checking games, in Proceedings of the 6th International Conference on Concurrency Theory, CONCUR '95, vol. 962 of Lecture Notes in Computer Science, pp. 1-11, Springer-Verlag, 1995.
[ List ]

@INPROCEEDINGS{Stirling95,
  AUTHOR = {Colin Stirling},
  TITLE = {Local Model Checking Games},
  BOOKTITLE = {Proceedings of the 6th International Conference on 
                   Concurrency Theory, CONCUR~'95},
  YEAR = {1995},
  PUBLISHER = {Springer-Verlag},
  PAGES = {1--11},
  SERIES = {Lecture Notes in Computer Science},
  VOLUME = {962},
  URL = {http://www.dcs.ed.ac.uk/home/cps/con95.ps}
}

[4] W. Thomas, On the synthesis of strategies in infinite games, in Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS '95, vol. 900 of Lecture Notes in Computer Science, pp. 1-13, Springer-Verlag, 1995.
[ List ]

@INPROCEEDINGS{Thomas95,
  AUTHOR = {Wolfgang Thomas},
  TITLE = {On the Synthesis of Strategies in Infinite Games},
  BOOKTITLE = {Proceedings of the 12th Annual Symposium on 
                   Theoretical Aspects of Computer Science, STACS~'95},
  YEAR = {1995},
  PUBLISHER = {Springer-Verlag},
  PAGES = {1--13},
  SERIES = {Lecture Notes in Computer Science},
  VOLUME = {900},
  URL = {http://www-i7.informatik.rwth-aachen.de/download/papers/thomas/thomas95a.ps}
}

[5] J. Vöge and M. Jurdzinski, A discrete strategy improvement algorithm for solving parity games, in Proceedings of the 12th International Conference on Computer Aided Verification, CAV 2000, vol. 1855 of Lecture Notes in Computer Science, pp. 202-215, Springer-Verlag, 2000.
[ List ]

@INPROCEEDINGS{VogeJ00,
  AUTHOR = {Jens V{\"o}ge and Marcin Jurdzi{\'n}ski},
  TITLE = {A Discrete Strategy Improvement Algorithm 
                   for Solving Parity Games},
  BOOKTITLE = {Proceedings of the 12th International Conference on 
                   Computer Aided Verification, CAV~2000},
  YEAR = {2000},
  PUBLISHER = {Springer-Verlag},
  PAGES = {202--215},
  SERIES = {Lecture Notes in Computer Science},
  VOLUME = {1855},
  URL = {http://www-cad.eecs.berkeley.edu/~mju/Papers/VJ00-CAV.ps}
}

[6] W. Zielonka, Infinite games on finitely coloured graphs with applications to automata on infinite trees, Theoretical Computer Science, vol. 200, no. 1-2, pp. 135-183, 1998.
[ List ]

@ARTICLE{Zielonka98,
  AUTHOR = {Wieslaw Zielonka},
  TITLE = {Infinite games on finitely coloured graphs 
                   with applications to automata on infinite trees},
  JOURNAL = {Theoretical Computer Science},
  VOLUME = {200},
  YEAR = {1998},
  PAGES = {135--183},
  NUMBER = {1--2}
}


 Webmaster  Email November 28, 2002 GAMES Home