{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T23:13:34Z","timestamp":1743030814237,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031369773"},{"type":"electronic","value":"9783031369780"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-36978-0_22","type":"book-chapter","created":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T11:03:01Z","timestamp":1689678181000},"page":"275-286","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Complexity Analysis of\u00a0Quasi-Polynomial Algorithms Solving Parity Games"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7247-1408","authenticated-orcid":false,"given":"Pawe\u0142","family":"Parys","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksander","family":"Wi\u0105cek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,19]]},"reference":[{"key":"22_CR1","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)"},{"issue":"2","key":"22_CR2","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s10703-018-0315-1","volume":"52","author":"M Benerecetti","year":"2018","unstructured":"Benerecetti, M., Dell\u2019Erba, D., Mogavero, F.: Solving parity games via priority promotion. Formal Meth. Syst. Des. 52(2), 193\u2013226 (2018)","journal-title":"Formal Meth. Syst. Des."},{"key":"22_CR3","unstructured":"Benerecetti, M., Dell\u2019Erba, D., Mogavero, F., Schewe, S., Wojtczak, D.: Priority promotion with Parysian flair. CoRR abs\/2105.01738 (2021)"},{"issue":"2","key":"22_CR4","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.dam.2006.04.029","volume":"155","author":"H Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Vorobyov, S.G.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discret. Appl. Math. 155(2), 210\u2013229 (2007)","journal-title":"Discret. Appl. Math."},{"key":"22_CR5","unstructured":"Boker, U., Lehtinen, K.: On the way to alternating weak automata. In: FSTTCS. LIPIcs, vol. 122, pp. 21:1\u201321:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"1\u20132","key":"22_CR6","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(96)00228-9","volume":"178","author":"A Browne","year":"1997","unstructured":"Browne, A., Clarke, E.M., Jha, S., Long, D.E., Marrero, W.R.: An improved algorithm for the evaluation of fixpoint expressions. Theor. Comput. Sci. 178(1\u20132), 237\u2013255 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR7","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. ACM (2017)","DOI":"10.1145\/3055399.3055409"},{"key":"22_CR8","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. SIAM (2019)","DOI":"10.1137\/1.9781611975482.142"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Continuous local search. In: SODA, pp. 790\u2013804. SIAM (2011)","DOI":"10.1137\/1.9781611973082.62"},{"key":"22_CR10","unstructured":"Daviaud, L., Jurdzi\u0144ski, M., Lehtinen, K.: Alternating weak automata from universal trees. In: CONCUR, LIPIcs, vol. 140, pp. 18:1\u201318:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"22_CR11","unstructured":"Daviaud, L., Jurdzi\u0144ski, M., Thejaswini, K.S.: The Strahler number of a parity game. In: ICALP. LIPIcs, vol. 168, pp. 123:1\u2013123:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Dell\u2019Erba, D., Schewe, S.: Smaller progress measures and separating automata for parity games. CoRR abs\/2205.00744 (2022)","DOI":"10.3389\/fcomp.2022.936903"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy (extended abstract). In: FOCS, pp. 368\u2013377. IEEE Computer Society (1991)","DOI":"10.1109\/SFCS.1991.185392"},{"issue":"1\u20132","key":"22_CR14","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/S0304-3975(00)00034-7","volume":"258","author":"EA Emerson","year":"2001","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model checking for the $$\\upmu $$-calculus and its fragments. Theor. Comput. Sci. 258(1\u20132), 491\u2013522 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-642-14162-1_46","volume-title":"Automata, Languages and Programming","author":"J Fearnley","year":"2010","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"},{"issue":"3","key":"22_CR16","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10009-019-00509-3","volume":"21","author":"J Fearnley","year":"2019","unstructured":"Fearnley, J., Jain, S., de Keijzer, B., Schewe, S., Stephan, F., Wojtczak, D.: An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space. Int. J. Softw. Tools Technol. Transfer 21(3), 325\u2013349 (2019)","journal-title":"Int. J. Softw. Tools Technol. Transfer"},{"key":"22_CR17","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":"22_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-642-20807-2_16","volume-title":"Integer Programming and Combinatoral Optimization","author":"O Friedmann","year":"2011","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"},{"key":"22_CR19","doi-asserted-by":"crossref","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)","DOI":"10.1145\/1993636.1993675"},{"issue":"3","key":"22_CR20","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M Jurdzi\u0144ski","year":"1998","unstructured":"Jurdzi\u0144ski, M.: Deciding the winner in parity games is in UP $$\\cap $$ co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998)","journal-title":"Inf. Process. Lett."},{"key":"22_CR21","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":"22_CR22","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, M., Lazi\u0107, R.: Succinct progress measures for solving parity games. In: LICS, pp. 1\u20139. IEEE Computer Society (2017)","DOI":"10.1109\/LICS.2017.8005092"},{"key":"22_CR23","unstructured":"Jurdzi\u0144ski, M., Morvan, R.: A universal attractor decomposition algorithm for parity games. CoRR abs\/2001.04333 (2020)"},{"key":"22_CR24","unstructured":"Jurdzi\u0144ski, M., Morvan, R., Ohlmann, P., Thejaswini, K.S.: A symmetric attractor-decomposition lifting algorithm for parity games. CoRR abs\/2010.08288 (2020)"},{"issue":"4","key":"22_CR25","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1137\/070686652","volume":"38","author":"M Jurdzi\u0144ski","year":"2008","unstructured":"Jurdzi\u0144ski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. SIAM J. Comput. 38(4), 1519\u20131532 (2008)","journal-title":"SIAM J. Comput."},{"key":"22_CR26","doi-asserted-by":"crossref","unstructured":"Lehtinen, K.: A modal $$\\mu $$ perspective on solving parity games in quasi-polynomial time. In: LICS, pp. 639\u2013648. ACM (2018)","DOI":"10.1145\/3209108.3209115"},{"issue":"1","key":"22_CR27","first-page":"1","volume":"18","author":"K Lehtinen","year":"2022","unstructured":"Lehtinen, K., Parys, P., Schewe, S., Wojtczak, D.: A recursive approach to solving parity games in quasipolynomial time. Log. Meth. Comput. Sci. 18(1), 1\u201318 (2022)","journal-title":"Log. Meth. Comput. Sci."},{"key":"22_CR28","unstructured":"Parys, P.: Parity games: Zielonka\u2019s algorithm in quasi-polynomial time. In: MFCS. LIPIcs, vol. 138, pp. 10:1\u201310:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"22_CR29","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/013","volume-title":"Automata on Infinite Objects and Church\u2019s Problem","author":"MO Rabin","year":"1972","unstructured":"Rabin, M.O.: Automata on Infinite Objects and Church\u2019s Problem. American Mathematical Society, Boston (1972)"},{"key":"22_CR30","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/j.jcss.2016.10.002","volume":"84","author":"S Schewe","year":"2017","unstructured":"Schewe, S.: Solving parity games in big steps. J. Comput. Syst. Sci. 84, 243\u2013262 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"22_CR31","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. Inf. Process. Lett. 59(6), 303\u2013308 (1996)","journal-title":"Inf. Process. Lett."},{"key":"22_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/10722167_18","volume-title":"Computer Aided Verification","author":"J V\u00f6ge","year":"2000","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"},{"issue":"1\u20132","key":"22_CR33","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. Theor. Comput. Sci. 200(1\u20132), 135\u2013183 (1998)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Unity of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-36978-0_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T10:33:42Z","timestamp":1729766022000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-36978-0_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031369773","9783031369780"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-36978-0_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"19 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Batumi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Georgia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 July 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.viam.science.tsu.ge\/cie2023","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1.1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13 invited abstracts have been included in the frontmatter","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}