Extracting Winning Strategies in Update Games

详细信息    查看全文

• 作者：Imran Khaliq (1) ikha020@aucklanduni.ac.nz
  Bakhadyr Khoussainov (1) bmk@cs.auckland.ac.nz
  Jiamou Liu (2) jiamou.liu@aut.ac.nz
• 刊名：Lecture Notes in Computer Science
• 出版年：2011
• 出版时间：2011
• 年：2011
• 卷：6735
• 期：1
• 页码：142-151
• 全文大小：196.2 KB
• 参考文献：1. Bodlaender, H.L., Dinneen, M.J., Khoussainov, B.: On Game-Theoretic Models of Networks. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol. 2223, pp. 550–561. Springer, Heidelberg (2001)
  2. Dinneen, M.J., Khoussainov, B.: Update Games and Update Networks. Journal of Discrete Algorithms 1(1) (2003)
  3. Dziembowski, S., Jurdzinski, M., Walukiewicz, I.: How Much Memory is Needed to Win Infinite Games. In: Proceedings of 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, pp. 99–110 (1997)
  4. Emerson, E.A., Jutla, C.S., Sistla, A.P.: On Model Checking for Fragments of μ-calculus. In: Courcoubetis, C. (ed.) CAV 1993. LNCS, vol. 697, pp. 385–396. Springer, Heidelberg (1993)
  5. Gr盲del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games. LNCS, vol. 2500. Springer, Heidelberg (2002)
  6. Ishihara, H., Khoussainov, B.: Complexity of Some Infinite Games Played on Finite Graphs. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 270–281. Springer, Heidelberg (2002)
  7. Mang, Y.C.: Games in open systems verification and synthesis. PhD Thesis, University of California at Berkeley (2002)
  8. McNaughton, R.: Infinite Games Played on Finite Graphs. Annals of Pure and Applied Logic 65, 149–184 (1993)
  9. Nerode, A., Remmel, J., Yakhnis, A.: McNaughton Games and Extracting Strategies for Concurrent Programs. Annals of Pure and Applied Logic 78, 203–242 (1996)
  10. Nerode, A., Yakhnis, A., Yakhnis, V.: Distributed Concurrent Programs as Strategies in Games. In: Logical Methods, pp. 624–653 (1992)
  11. Hunter, P., Dawar, A.: Complexity Bounds for Regular Games. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 495–506. Springer, Heidelberg (2005)
  12. Tarjan, R.: Depth-first Search and Linear Graph Algorithms. SIAM Journal on Computing 1, 146–160 (1972)
  13. Thomas, W.: Infinite games and verification (Extended abstract of a tutorial). In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 58–64. Springer, Heidelberg (2002)
• 作者单位：1. Department of Computer Science, University of Auckland, New Zealand2. School of Computing and Mathematical Sciences, Auckland University of Technology, New Zealand
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

This paper investigates algorithms for extracting winning strategies in two-player games played on finite graphs. We focus on a special class of games called update games. We present a procedure for extracting winning strategies in update games by constructing strategies explicitly. This is based on an algorithm that solves update games in quadratic time. We also show that solving update games with a bounded number of nonkdeterministic nodes takes linear time.