Faster Solutions of Rabin and Streett Games
Authors:
- N. PitermanNPN. Piterman
- A. PnueliAPA. Pnueli
- 22 September 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10436871,p. 275-284
Abstract
In this paper we improve the complexity of solving Rabin and Streett games to approximately the square root of previous bounds. We introduce direct Rabin and Streett ranking that are a sound and complete way to characterize the winning sets in the respective games. By computing directly and explicitly the ranking we can solve such games in time O(mnk+1kk!) and space O(nk) for Rabin and O(nkk!) for Streett where n is the number of states, m the number of transitions, and k the number of pairs in the winning condition. In order to prove completeness of the ranking method we give a recursive fixpoint characterization of the winning regions in these games. We then show that by keeping intermediate values during the fixpoint evaluation, we can solve such games symbolically in time O(nk+1k!) and space O(nk+1k!). These results improve on the current bounds of O(mn2kk!) time in the case of direct (symbolic) solution or O(m(nk2k!)k) in the case of reduction to parity gamesKeywords
This publication has 15 references indexed in Scilit:
- A Discrete Subexponential Algorithm for Parity GamesLecture Notes in Computer Science, 2003
- How much memory is needed to win infinite games?2002
- Infinite games on finitely coloured graphs with applications to automata on infinite treesTheoretical Computer Science, 1998
- Progress measures, immediate determinacy, and a subset construction for tree automataAnnals of Pure and Applied Logic, 1994
- Infinite games played on finite graphsAnnals of Pure and Applied Logic, 1993
- Automata on Infinite Objects1990
- Propositional dynamic logic of looping and converse is elementarily decidableInformation and Control, 1982
- Trees, automata, and games1982
- Decidability of Second-Order Theories and Automata on Infinite TreesTransactions of the American Mathematical Society, 1969
- Solving Sequential Conditions by Finite-State StrategiesTransactions of the American Mathematical Society, 1969