{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:11:09Z","timestamp":1780632669220,"version":"3.54.1"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031223365","type":"print"},{"value":"9783031223372","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22337-2_12","type":"book-chapter","created":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:08:41Z","timestamp":1672222121000},"page":"252-271","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Universal Algorithms for\u00a0Parity Games and\u00a0Nested Fixpoints"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3640-8481","authenticated-orcid":false,"given":"Marcin","family":"Jurdzi\u0144ski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1418-3405","authenticated-orcid":false,"given":"R\u00e9mi","family":"Morvan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K. S.","family":"Thejaswini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,12,29]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Apt, K.R., Gr\u00e4del, E. (eds.): Lectures in Game Theory for Computer Scientists. Cambridge University Press (2011). http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item5760379","DOI":"10.1017\/CBO9780511973468"},{"key":"12_CR2","doi-asserted-by":"publisher","unstructured":"Arnold, A., Niwi\u0144ski, D., Parys, P.: A quasi-polynomial black-box algorithm for fixed point evaluation. In: CSL. LIPIcs, vol. 183, pp. 9:1\u20139:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2021.9, https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2021.9","DOI":"10.4230\/LIPIcs.CSL.2021.9"},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Baldan, P., K\u00f6nig, B., Mika-Michalski, C., Padoan, T.: Fixpoint games on continuous lattices. Proc. ACM Program. Lang. 3(POPL) (2019). https:\/\/doi.org\/10.1145\/3290339, https:\/\/doi.org\/10.1145\/3290339","DOI":"10.1145\/3290339"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"Bradfield, J.C., Walukiewicz, I.: The mu-calculus and model checking. In: Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R. (eds.) Handbook of Model Checking, pp. 871\u2013919. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-10575-8_26, https:\/\/doi.org\/10.1007\/978-3-319-10575-8_26","DOI":"10.1007\/978-3-319-10575-8_26"},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Burch, J.R., Clarke, E.M., McMillan, K.L., Dill, D.L., Hwang, L.J.: Symbolic model checking: $$10{\\hat{\\,}}20$$ states and beyond. Inf. Comput. 98(2), 142\u2013170 (1992). https:\/\/doi.org\/10.1016\/0890-5401(92)90017-A, https:\/\/doi.org\/10.1016\/0890-5401(92)90017-A","DOI":"10.1016\/0890-5401(92)90017-A"},{"key":"12_CR6","doi-asserted-by":"publisher","unstructured":"Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasipolynomial time. In: STOC, pp. 252\u2013263 (2017). https:\/\/doi.org\/10.1145\/3055399.3055409","DOI":"10.1145\/3055399.3055409"},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Alfaro, L.D., Henzinger, T.A.: Qualitative concurrent parity games. ACM Trans. Comput. Logic 12(4) (2011). https:\/\/doi.org\/10.1145\/1970398.1970404, https:\/\/doi.org\/10.1145\/1970398.1970404","DOI":"10.1145\/1970398.1970404"},{"key":"12_CR8","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Dvo\u0159\u00e1k, W., Henzinger, M., Svozil, A.: Quasipolynomial set-based symbolic algorithms for parity games. In: LPAR-22. EPiC Series in Computing, vol. 57, pp. 233\u2013253 (2018). https:\/\/doi.org\/10.29007\/5z5k","DOI":"10.29007\/5z5k"},{"key":"12_CR9","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/1.9781611975482.142","DOI":"10.1137\/1.9781611975482.142"},{"key":"12_CR10","doi-asserted-by":"publisher","unstructured":"Daviaud, L., Jurdzi\u0144ski, M., Lazi\u0107, R.: A pseudo-quasi-polynomial algorithm for mean-payoff parity games. In: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2018, 09\u201312 July 2018. pp. 325\u2013334. ACM, Oxford, UK (2018). https:\/\/doi.org\/10.1145\/3209108.3209162, https:\/\/doi.org\/10.1145\/3209108.3209162","DOI":"10.1145\/3209108.3209162"},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"Daviaud, L., Jurdzi\u0144ski, M., Lehtinen, K.: Alternating weak automata from universal trees. In: CONCUR 2019, 27\u201330 August 2019, pp. 18:1\u201318:14. LIPIcs (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2019.18, https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2019.18","DOI":"10.4230\/LIPIcs.CONCUR.2019.18"},{"key":"12_CR12","doi-asserted-by":"publisher","unstructured":"Daviaud, L., Jurdzi\u0144ski, M., Thejaswini, K.S.: The strahler number of a parity game. In: ICALP 2020, 8\u201311 July 2020, vol. 168, pp. 123:1\u2013123:19. LIPIcs (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.123","DOI":"10.4230\/LIPIcs.ICALP.2020.123"},{"key":"12_CR13","doi-asserted-by":"publisher","unstructured":"Dijk, T.: Oink: an implementation and evaluation of modern parity game solvers. In: Beyer, D., Huisman, M. (eds.) TACAS 2018. LNCS, vol. 10805, pp. 291\u2013308. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-89960-2_16","DOI":"10.1007\/978-3-319-89960-2_16"},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Emerson, E.A., Jutla, C.: Tree automata, mu-calculus and determinacy. In: FOCS, pp. 368\u2013377 (1991). https:\/\/doi.org\/10.1109\/SFCS.1991.185392","DOI":"10.1109\/SFCS.1991.185392"},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model-checking for fragments of $$\\mu $$-calculus. In: Courcoubetis, C. (ed.) CAV 1993. LNCS, vol. 697, pp. 385\u2013396. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-56922-7_32","DOI":"10.1007\/3-540-56922-7_32"},{"key":"12_CR16","doi-asserted-by":"publisher","unstructured":"Etessami, K., Wilke, T., Schuller, R.A.: Fair simulation relations, parity games, and state space reduction for B\u00fcchi automata. SIAM J. Comput. 34(5), 1159\u20131175 (2005). https:\/\/doi.org\/10.1137\/S0097539703420675, https:\/\/doi.org\/10.1137\/S0097539703420675","DOI":"10.1137\/S0097539703420675"},{"key":"12_CR17","doi-asserted-by":"publisher","unstructured":"Fearnley, J.: exponential lower bounds for policy iteration. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 551\u2013562. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14162-1_46","DOI":"10.1007\/978-3-642-14162-1_46"},{"key":"12_CR18","doi-asserted-by":"publisher","unstructured":"Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11\u201314 August 2009,pp. 145\u2013156. IEEE Computer Society, Los Angeles, CA, USA (2009). https:\/\/doi.org\/10.1109\/LICS.2009.27, https:\/\/doi.org\/10.1109\/LICS.2009.27","DOI":"10.1109\/LICS.2009.27"},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Friedmann, O.: Recursive algorithm for parity games requires exponential time. RAIRO Theor. Inform. Appl. 45(4), 449\u2013457 (2011). https:\/\/doi.org\/10.1051\/ita\/2011124, https:\/\/doi.org\/10.1051\/ita\/2011124","DOI":"10.1051\/ita\/2011124"},{"key":"12_CR20","doi-asserted-by":"publisher","unstructured":"Friedmann, O.: a subexponential lower bound for zadeh\u2019s pivoting rule for solving linear programs and games. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 192\u2013206. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20807-2_16","DOI":"10.1007\/978-3-642-20807-2_16"},{"key":"12_CR21","doi-asserted-by":"publisher","unstructured":"Friedmann, O., Hansen, T.D., Zwick, U.: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In: STOC, pp. 283\u2013292. ACM (2011). https:\/\/doi.org\/10.1145\/1993636.1993675, https:\/\/doi.org\/10.1145\/1993636.1993675","DOI":"10.1145\/1993636.1993675"},{"key":"12_CR22","doi-asserted-by":"publisher","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], LNCS, vol.\u00a02500. Springer (2002). https:\/\/doi.org\/10.1007\/3-540-36387-4, https:\/\/doi.org\/10.1007\/3-540-36387-4","DOI":"10.1007\/3-540-36387-4"},{"key":"12_CR23","doi-asserted-by":"publisher","unstructured":"Hasuo, I., Shimizu, S., C\u00eerstea, C.: Lattice-theoretic progress measures and coalgebraic model checking. In: POPL, pp. 718\u2013732. ACM (2016). https:\/\/doi.org\/10.1145\/2837614.2837673, https:\/\/doi.org\/10.1145\/2837614.2837673","DOI":"10.1145\/2837614.2837673"},{"key":"12_CR24","doi-asserted-by":"publisher","unstructured":"Hausmann, D., Schr\u00f6der, L.: Optimal satisfiability checking for arithmetic $$\\mu $$-Calculi. In: Boja\u0144czyk, M., Simpson, A. (eds.) FoSSaCS 2019. LNCS, vol. 11425, pp. 277\u2013294. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17127-8_16","DOI":"10.1007\/978-3-030-17127-8_16"},{"key":"12_CR25","doi-asserted-by":"publisher","unstructured":"Hausmann, D., Schr\u00f6der, L.: Quasipolynomial computation of nested fixpoints. In: TACAS 2021. LNCS, vol. 12651, pp. 38\u201356. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-72016-2_3","DOI":"10.1007\/978-3-030-72016-2_3"},{"key":"12_CR26","doi-asserted-by":"publisher","unstructured":"Jurdzi\u0144ski, M., Lazi\u0107, R.: Succinct progress measures for solving parity games. In: LICS, pp. 1\u20139 (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005092","DOI":"10.1109\/LICS.2017.8005092"},{"key":"12_CR27","doi-asserted-by":"publisher","unstructured":"Lehtinen, K.: A modal $$\\mu $$ perspective on solving parity games in quasi-polynomial time. In: LICS, pp. 639\u2013648 (2018). https:\/\/doi.org\/10.1145\/3209108.3209115","DOI":"10.1145\/3209108.3209115"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Lehtinen, K., Parys, P., Schewe, S., Wojtczak, D.: A recursive approach to solving parity games in quasipolynomial time. Logical Methods Comput. Sci. 18(1), 10 (2022). 46298\/lmcs-18(1:8)2022, https:\/\/lmcs.episciences.org\/8953","DOI":"10.46298\/lmcs-18(1:8)2022"},{"key":"12_CR29","doi-asserted-by":"publisher","unstructured":"Lehtinen, K., Schewe, S., Wojtczak, D.: Improving the complexity of Parys\u2019 recursive algorithm. arXiv:1904.11810 (2019). https:\/\/doi.org\/10.48550\/arXiv.1904.11810","DOI":"10.48550\/arXiv.1904.11810"},{"key":"12_CR30","doi-asserted-by":"publisher","unstructured":"Luttenberger, M., Meyer, P.J., Sickert, S.: Practical synthesis of reactive systems from LTL specifications via parity games. Acta Informatica 57(1-2), 3\u201336 (2020). https:\/\/doi.org\/10.1007\/s00236-019-00349-3, https:\/\/doi.org\/10.1007\/s00236-019-00349-3","DOI":"10.1007\/s00236-019-00349-3"},{"issue":"2","key":"12_CR31","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). https:\/\/doi.org\/10.1016\/0168-0072(93)90036-D","journal-title":"Ann. Pure Appl. Logic"},{"key":"12_CR32","doi-asserted-by":"publisher","unstructured":"Parys, P.: Parity games: Zielonka\u2019s algorithm in quasi-polynomial time. In: 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.10","DOI":"10.4230\/LIPIcs.MFCS.2019.10"},{"issue":"6","key":"12_CR33","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0020-0190(96)00130-5","volume":"59","author":"H Seidl","year":"1996","unstructured":"Seidl, H.: Fast and simple nested fixpoints. Inform. Process. Let. 59(6), 303\u2013308 (1996). https:\/\/doi.org\/10.1016\/0020-0190(96)00130-5","journal-title":"Inform. Process. Let."},{"key":"12_CR34","doi-asserted-by":"publisher","unstructured":"V\u00f6ge, J., Jurdzi\u0144ski, 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\u2013215. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10722167_18","DOI":"10.1007\/10722167_18"},{"key":"12_CR35","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(98)00009-7","volume":"200","author":"W Zielonka","year":"1998","unstructured":"Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Comput. Sci. 200, 135\u2013183 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(98)00009-7","journal-title":"Theoretical Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Principles of Systems Design"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22337-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T00:07:59Z","timestamp":1672358879000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22337-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031223365","9783031223372"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22337-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 December 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}