Local Strategy Improvement for Parity Game Solving

Article, Preprint English OPEN
Friedmann, Oliver; Lange, Martin;
(2010)
  • 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.13
  • Subject: Mathematics | Computer Science - Computer Science and Game Theory | Computer Science - Computational Complexity | Computer Science - Data Structures and Algorithms | Electronic computers. Computer science | Computer Science - Logic in Computer Science | QA1-939 | QA75.5-76.95
    arxiv: Computer Science::Computer Science and Game Theory

The problem of solving a parity game is at the core of many problems in model checking, satisfiability checking and program synthesis. Some of the best algorithms for solving parity game are strategy improvement algorithms. These are global in nature since they require ... View more
  • References (14)
    14 references, page 1 of 2

    [1] A. Arnold, A. Vincent & I. Walukiewicz (2003): Games for synthesis of controllers with partial observation. Theor. Comput. Sci. 303(1), pp. 7-34.

    [2] G. Bhat & R. Cleaveland (1996): Efficient Local Model-Checking for Fragments of the Modal μ -Calculus. In: Proc. 2nd Int. Workshop on Tools and Algorithms for Construction and Analysis of Systems, TACAS'96, LNCS 1055, Springer, pp. 107-126.

    [3] E. A. Emerson & C. S. Jutla (1991): Tree Automata, μ -Calculus and Determinacy. In: Proc. 32nd Symp. on Foundations of Computer Science, IEEE, San Juan, Puerto Rico, pp. 368-377.

    [4] O. Friedmann & M. Lange (2009): Solving Parity Games in Practice. In: Proc. 7th Int. Symp. on Automated Technology for Verification and Analysis, ATVA'09, LNCS 5799, pp. 182-196.

    [5] O. Friedmann & M. Lange (2009): Tableaux with Automata. In: Proc. Workshop on Tableaux vs. Automata as Logical Decision Procedures, AutoTab'09.

    [6] M. Jurdzin´ ski (1998): Deciding the winner in parity games is in U P∩co-U P. Inf. Process. Lett. 68(3), pp. 119-124.

    [7] M. Jurdzin´ ski (2000): Small progress measures for solving parity games. In: Proc. 17th Ann. Symp. on Theoretical Aspects of Computer Science, STACS'00, LNCS 1770, Springer, pp. 290-301.

    [8] M. Lange & C. Stirling (2002): Model checking games for branching time logics. Journal of Logic and Computation 12(4), pp. 623-639.

    [9] A. Puri (1995): Theory of hybrid systems and discrete event systems. Ph.D. thesis, University of California, Berkeley.

    [10] S. Schewe (2008): An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games. In: Proc. 17th Ann. Conf. on Computer Science Logic, CSL'08, LNCS 5213, Springer, pp. 369-384.

  • Related Organizations (1)
  • Metrics
Share - Bookmark