Abstract
We first consider infinite two-player games on pushdown graphs. In previous work, Cachat, Duparc and Thomas [4] have presented a winning decidable condition that is Σ3-complete in the Borel hierarchy. This was the first example of a decidable winning condition of such Borel complexity. We extend this result by giving a family of decidable winning conditions of arbitrary high finite Borel complexity. From this family, we deduce a family of decidable winning conditions of arbitrary finite Borel complexity for games played on finite graphs. The problem of deciding the winner for these winning conditions is shown to be non-elementary complete.
This research has been partially supported by the European Community Research Training Network “Games and Automata for Synthesis and Validation” (GAMES), (contract HPRN-CT-2002-00283), see www.games.rwth-aachen.de.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arnold, A., Vincent, A., Walukiewicz, I.: Games for synthesis of controlers with partial observation. Theoretical Computer Science 303(1), 7–34 (2003)
Bouquet, A., Serre, O., Walukiewicz, I.: Pushdown games with the unboundedness and regular conditions. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol. 2914, pp. 88–99. Springer, Heidelberg (2003)
Cachat, T.: Uniform solution of parity games on prefix-recognizable graphs. Electronic Notes in Theoretical Computer Science, vol. 68. Elsevier, Amsterdam (2002)
Cachat, T., Duparc, J., Thomas, W.: Solving pushdown games with a Σ3 winning condition. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. T. Cachat, J. Duparc, and W. Thomas, vol. 2471, pp. 322–336. Springer, Heidelberg (2002)
Duparc, J.: Wadge hierarchy and Veblen hierarchy. part I: Borel sets of finite rank. Journal of Symbolic Logic 66(1), 56–86 (2001)
Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model-checking for the mu-calculus and its fragments. Theoretical Computer Science 258(1-2), 491–522 (2001)
Jurdziński, M.: Small progress measures for solving parity games. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 290–301. Springer, Heidelberg (2000)
Marcinkowski, J., Truderung, T.: Optimal complexity bounds for positive LTL games. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol. 2471, pp. 262–275. Springer, Heidelberg (2002)
Martin, D.A.: Borel determinacy. Annals of Mathematics 102, 363–371 (1975)
Serre, O.: Note on winning positions on pushdown games with ω-regular conditions. Information Processing Letters 85, 285–291 (2003)
Thomas, W.: On the synthesis of strategies in infinite games. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol. 900, pp. 1–13. Springer, Heidelberg (1995)
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)
Vöge, J., Jurdziński, M.: A discrete strategy improvement algorithm for solving parity games. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 202–215. Springer, Heidelberg (2000)
Walukiewicz, I.: Pushdown processes: games and model checking. Information and Computation 157, 234–263 (2000)
Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science 200(1-2), 135–183 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Serre, O. (2004). Games with Winning Conditions of High Borel Complexity. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_95
Download citation
DOI: https://doi.org/10.1007/978-3-540-27836-8_95
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22849-3
Online ISBN: 978-3-540-27836-8
eBook Packages: Springer Book Archive