Omega-Regular Half-Positional Winning Conditions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Omega-Regular Half-Positional Winning Conditions

  • Conference paper
Computer Science Logic (CSL 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4646))

Included in the following conference series:

  • 831 Accesses

Abstract

We study infinite games where one of the players always has a positional (memory-less) winning strategy, while the other player may use a history-dependent strategy. We investigate winning conditions which guarantee such a property for all arenas, or all finite arenas. Our main result is that this property is decidable in single exponential time for a given prefix independent ω-regular winning condition. We also exhibit a big class of winning conditions (XPS) which has this property.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  • Colcombet, T., Niwiński, D.: On the positional determinacy of edge-labeled games. Theor. Comput. Sci. 352, 190–196 (2006)

    Article  MATH  Google Scholar 

  • Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy. In: Proceedings 32th Annual IEEE Symp. on Foundations of Comput. Sci., pp. 368–377. IEEE Computer Society Press, Los Alamitos (1991)

    Google Scholar 

  • Grädel, E.: Positional Determinacy of Infinite Games. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 4–18. Springer, Heidelberg (2004)

    Google Scholar 

  • Grädel, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games. LNCS, vol. 2500. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  • Grädel, E., Walukiewicz, I.: Positional determinacy of games with infinitely many priorities. Logical Methods in Computer Science 2(4:6), 1–22 (2006)

    Google Scholar 

  • Gimbert, H., Zielonka, W.: When can you play positionally? In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 686–697. Springer, Heidelberg (2004)

    Google Scholar 

  • Gimbert, H., Zielonka, W.: Games Where You Can Play Optimally Without Any Memory. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 428–442. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  • Klarlund, N.: Progress measures, immediate determinacy, and a subset construction for tree automata. In: Proc. 7th IEEE Symp. on Logic in Computer Science (1992)

    Google Scholar 

  • Kopczyński, E.: Half-Positional Determinacy of Infinite Games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 336–347. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  • Kopczyński, E.: Half-positional determinacy of infinite games. Draft. http://www.mimuw.edu.pl/~erykk/papers/hpwc.ps

  • Martin, D.A.: Borel determinacy. Ann. Math. 102, 363–371 (1975)

    Article  Google Scholar 

  • McNaughton, R.: Infinite games played on finite graphs. Annals of Pure and Applied Logic 65, 149–184 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  • Mostowski, A.W.: Games with forbidden positions. Technical Report 78, Uniwersytet Gdański, Instytut Matematyki (1991)

    Google Scholar 

  • Zielonka, W.: Infinite Games on Finitely Coloured Graphs with Applications to Automata on Infinite Trees. Theor. Comp. Sci. 200(1-2), 135–183 (1998)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Informatics, Warsaw University,  

    Eryk Kopczyński

Authors
  1. Eryk Kopczyński
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jacques Duparc Thomas A. Henzinger

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kopczyński, E. (2007). Omega-Regular Half-Positional Winning Conditions. In: Duparc, J., Henzinger, T.A. (eds) Computer Science Logic. CSL 2007. Lecture Notes in Computer Science, vol 4646. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74915-8_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-74915-8_7

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-74914-1

  • Online ISBN: 978-3-540-74915-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics