{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:07Z","timestamp":1753894387010,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014013","name":"UK Research and Innovation","doi-asserted-by":"crossref","award":["EP\/P020909\/1"],"award-info":[{"award-number":["EP\/P020909\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["892704"],"award-info":[{"award-number":["892704"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Zielonka's classic recursive algorithm for solving parity games is perhaps\nthe simplest among the many existing parity game algorithms. However, its\ncomplexity is exponential, while currently the state-of-the-art algorithms have\nquasipolynomial complexity. Here, we present a modification of Zielonka's\nclassic algorithm that brings its complexity down to\n$n^{O\\left(\\log\\left(1+\\frac{d}{\\log n}\\right)\\right)}$, for parity games of\nsize $n$ with $d$ priorities, in line with previous quasipolynomial-time\nsolutions.<\/jats:p>","DOI":"10.46298\/lmcs-18(1:8)2022","type":"journal-article","created":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T17:32:04Z","timestamp":1642095124000},"source":"Crossref","is-referenced-by-count":7,"title":["A Recursive Approach to Solving Parity Games in Quasipolynomial Time"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"given":"Karoliina","family":"Lehtinen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7247-1408","authenticated-orcid":false,"given":"Pawe\u0142","family":"Parys","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9093-9518","authenticated-orcid":false,"given":"Sven","family":"Schewe","sequence":"additional","affiliation":[]},{"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2022,1,12]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/8953\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/8953\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:19:50Z","timestamp":1687292390000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/7387"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:8)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2104.09717v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2104.09717v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2104.09717","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2104.09717","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"article-number":"7387"}}