GAMES RTN > Warsaw Team > Research Task 6

Task 6: Game models for protocols

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.

• presentation of Task 6 (by Damian Niwinski and Jerzy Tyszkiewicz) in Edinburgh. [materials]
• Discussions on the above (to follow).

[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. [ BibTeX ]
[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. [ BibTeX ]
[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. [ BibTeX ]
[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. [ BibTeX ]
[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. [ BibTeX ]
[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. [ BibTeX ]