Playing Muller Games in a Hurry

Article, Preprint English OPEN
John Fearnley; Martin Zimmermann;
  • Publisher: Open Publishing Association
  • Journal: Electronic Proceedings in Theoretical Computer Science (issn: 2075-2180)
  • Publisher copyright policies & self-archiving
  • Related identifiers: doi: 10.4204/EPTCS.25.15
  • Subject: Mathematics | Computer Science - Computer Science and Game Theory | Electronic computers. Computer science | Computer Science - Logic in Computer Science | QA1-939 | QA75.5-76.95
    acm: ComputingMilieux_PERSONALCOMPUTING
    arxiv: Computer Science::Computer Science and Game Theory

This work studies the following question: can plays in a Muller game be stopped after a finite number of moves and a winner be declared. A criterion to do this is sound if Player 0 wins an infinite-duration Muller game if and only if she wins the finite-duration version... View more
  • References (11)
    11 references, page 1 of 2

    [1] Julius R. Bu¨chi & Lawrence H. Landweber (1969): Solving Sequential Conditions by Finite-state Strategies. Trans. Amer. Math. Soc. 138, pp. 295-311.

    [2] Krishnendu Chatterjee, Thomas A. Henzinger & Florian Horn (2009): Finitary winning in omega-regular games. ACM Trans. Comput. Log. 11(1). Available at 1614432.

    [3] Stefan Dziembowski, Marcin Jurdzin´ski & Igor Walukiewicz (1997): How Much Memory is Needed to Win Infinite Games? In: LICS, pp. 99-110. Available at 7925/79250099abs.htm.

    [4] Stefan Dziembowski, Marcin Jurdzin´ski & Igor Walukiewicz (1998): How Much Memory is Needed to Win Infinite Games? Available at Unfinished draft of [3].

    [5] Yuri Gurevich & Leo Harrington (1982): Trees, Automata, and Games. In: STOC, ACM, pp. 60-65.

    [6] Florian Horn, Wolfgang Thomas & Nico Wallmeier (2008): Optimal Strategy Synthesis in Request-Response Games. In: Sung Deok Cha, Jin-Young Choi, Moonzoo Kim, Insup Lee & Mahesh Viswanathan, editors: ATVA, Lecture Notes in Computer Science 5311, Springer, pp. 361-373. Available at http://dx.doi. org/10.1007/978-3-540-88387-6_31.

    [7] Robert McNaughton (1993): Infinite Games Played on Finite Graphs. Ann. Pure Appl. Logic 65(2), pp. 149-184.

    [8] Robert McNaughton (2000): Playing Infinite Games in Finite Time. In: Arto Salomaa, Derick Wood & Sheng Yu, editors: A Half-Century of Automata Theory, World Scientific, pp. 73-91.

    [9] Ernst Zermelo (1913): U¨ ber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In: Proc. of the Fifth Congress of Mathematicians, Vol. 2, Cambridge Press, pp. 501-504.

    [10] Wieslaw Zielonka (1998): Infinite Games on Finitely Coloured Graphs with Applications to Automata on Infinite Trees. Theor. Comput. Sci. 200(1-2), pp. 135-183. Available at S0304-3975(98)00009-7.

  • Similar Research Results (1)
  • Metrics
Share - Bookmark