{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:41:43Z","timestamp":1757616103321,"version":"3.44.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030171261"},{"type":"electronic","value":"9783030171278"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":94,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this paper, we give a self contained presentation of a recent breakthrough in the theory of infinite duration games: the existence of a quasipolynomial time algorithm for solving parity games. We introduce for this purpose two new notions: good for small games automata and universal graphs.<\/jats:p>\n          <jats:p>The first object, good for small games automata, induces a generic algorithm for solving games by reduction to safety games. We show that it is in a strong sense equivalent to the second object, universal graphs, which is a combinatorial notion easier to reason with. Our equivalence result is very generic in that it holds for all existential memoryless winning conditions, not only for parity conditions.<\/jats:p>","DOI":"10.1007\/978-3-030-17127-8_1","type":"book-chapter","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T11:11:46Z","timestamp":1554462706000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Universal Graphs and Good for Games Automata: New Tools for Infinite Duration Games"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Colcombet","sequence":"first","affiliation":[]},{"given":"Nathana\u00ebl","family":"Fijalkow","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"1_CR1","unstructured":"Boja\u0144czyk, M., Czerwi\u0144ski, W.: An automata toolbox, February 2018. https:\/\/www.mimuw.edu.pl\/~bojan\/papers\/toolbox-reduced-feb6.pdf"},{"key":"1_CR2","unstructured":"Boker, U., Kupferman, O., Skrzypczak, M.: How deterministic are good-for-games automata? In: FSTTCS, pp. 18:1\u201318:14 (2017)"},{"issue":"2","key":"1_CR3","doi-asserted-by":"publisher","first-page":"166","DOI":"10.2307\/2271090","volume":"34","author":"JR B\u00fcchi","year":"1969","unstructured":"B\u00fcchi, J.R., Landweber, L.H.: Definability in the monadic second-order theory of successor. J. Symbolic Logic 34(2), 166\u2013170 (1969)","journal-title":"J. Symbolic Logic"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Boker, U., Lehtinen, K.: Register games. Logical Methods Comput. Sci. (Submitted, 2019)","DOI":"10.23638\/LMCS-16(2:6)2020"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Czerwi\u0144ski, W., Daviaud, L., Fijalkow, N., Jurdzi\u0144ski, M., Lazi\u0107, R., Parys, P.: Universal trees grow inside separating automata: quasi-polynomial lower bounds for parity games. In: SODA, pp. 2333\u20132349 (2019)","DOI":"10.1137\/1.9781611975482.142"},{"key":"1_CR6","unstructured":"Colcombet, T., Fijalkow, N.: Parity games and universal graphs. CoRR, abs\/1810.05106 (2018)"},{"key":"1_CR7","unstructured":"Colcombet, T., Fijalkow, N., Horn, F.: Playing safe. In: FSTTCS, pp. 379\u2013390 (2014)"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasipolynomial time. In: STOC, pp. 252\u2013263 (2017)","DOI":"10.1145\/3055399.3055409"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy (extended abstract). In: FOCS, pp. 368\u2013377 (1991)","DOI":"10.1109\/SFCS.1991.185392"},{"issue":"8","key":"1_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01768705","volume":"109","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 109(8), 109\u2013113 (1979)","journal-title":"Int. J. Game Theory"},{"key":"1_CR11","unstructured":"Fijalkow, N., Gawrychowski, P., Ohlmann, P.: The complexity of mean payoff games using universal graphs. CoRR, abs\/1812.07072 (2018)"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Fijalkow, N.: An optimal value iteration algorithm for parity games. CoRR, abs\/1801.09618 (2018)","DOI":"10.29007\/k2nm"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Gurevich, Y., Harrington, L.: Trees, automata, and games. In: STOC, pp. 60\u201365 (1982)","DOI":"10.1145\/800070.802177"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"VA Gurvich","year":"1988","unstructured":"Gurvich, V.A., Karzanov, A.V., Khachiyan, L.G.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Comput. Math. Math. Phys. 28, 85\u201391 (1988)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/11874683_26","volume-title":"Computer Science Logic","author":"TA Henzinger","year":"2006","unstructured":"Henzinger, T.A., Piterman, N.: Solving games without determinization. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 395\u2013410. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11874683_26"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, M., Lazi\u0107, R.: Succinct progress measures for solving parity games. In: LICS, pp. 1\u20139 (2017)","DOI":"10.1109\/LICS.2017.8005092"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/3-540-46541-3_24","volume-title":"STACS 2000","author":"M Jurdzi\u0144ski","year":"2000","unstructured":"Jurdzi\u0144ski, M.: Small progress measures for solving parity games. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 290\u2013301. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-46541-3_24"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Lehtinen, K.: A modal-\n$$\\mu $$\n perspective on solving parity games in quasi-polynomial time. In: LICS, pp. 639\u2013648 (2018)","DOI":"10.1145\/3209108.3209115"},{"issue":"2","key":"1_CR19","doi-asserted-by":"publisher","first-page":"363","DOI":"10.2307\/1971035","volume":"102","author":"DA Martin","year":"1975","unstructured":"Martin, D.A.: Borel determinacy. Ann. Math. 102(2), 363\u2013371 (1975)","journal-title":"Ann. Math."},{"issue":"2","key":"1_CR20","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0168-0072(93)90036-D","volume":"65","author":"R McNaughton","year":"1993","unstructured":"McNaughton, R.: Infinite games played on finite graphs. Ann. Pure Appl. Logic 65(2), 149\u2013184 (1993)","journal-title":"Ann. Pure Appl. Logic"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17127-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T16:23:56Z","timestamp":1757089436000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17127-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030171261","9783030171278"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17127-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2019\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}