{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T17:40:07Z","timestamp":1756489207378,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["CoG 863818 (ForM-SMArt)"],"award-info":[{"award-number":["CoG 863818 (ForM-SMArt)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,7,8]]},"DOI":"10.1145\/3661814.3662080","type":"proceedings-article","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T08:30:12Z","timestamp":1718958612000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-2839-953X","authenticated-orcid":false,"given":"Ali","family":"Asadi","sequence":"first","affiliation":[{"name":"CS, Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4561-241X","authenticated-orcid":false,"given":"Krishnendu","family":"Chatterjee","sequence":"additional","affiliation":[{"name":"CS, Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1419-3267","authenticated-orcid":false,"given":"Jakub","family":"Svoboda","sequence":"additional","affiliation":[{"name":"Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5103-038X","authenticated-orcid":false,"given":"Raimundo","family":"Saona Urmeneta","sequence":"additional","affiliation":[{"name":"Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria"}]}],"member":"320","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Improved combinatorial algorithms for discounted payoff games. Master's thesis","author":"Andersson D.","year":"2006","unstructured":"Andersson, D. Improved combinatorial algorithms for discounted payoff games. Master's thesis, Uppsala University, 2006."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_13"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/noti2789"},{"key":"e_1_3_2_1_4_1","unstructured":"Bansal S. Chatterjee K. and Vardi M. Y. On satisficing in quantitative games. Tools and Algorithms for the Construction and Analysis of Systems 12651 20."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611599011831"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-010-0105-x"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1145288"},{"key":"e_1_3_2_1_8_1","volume-title":"Journal of the ACM (JACM) 28, 1","author":"Chandra A. K.","year":"1981","unstructured":"Chandra, A. K., Kozen, D. C., and Stockmeyer, L. J. Alternation. Journal of the ACM (JACM) 28, 1 (1981), 114--133."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.54.6"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1403375.1403595"},{"key":"e_1_3_2_1_11_1","volume-title":"Efficient and dynamic algorithms for alternating b\u00fcchi games and maximal end-component decomposition. Journal of the ACM (JACM) 61, 3","author":"Chatterjee K.","year":"2014","unstructured":"Chatterjee, K., and Henzinger, M. Efficient and dynamic algorithms for alternating b\u00fcchi games and maximal end-component decomposition. Journal of the ACM (JACM) 61, 3 (2014), 1--40."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676968"},{"key":"e_1_3_2_1_13_1","volume-title":"On Algorithms for Simple Stochastic Games. Advances in computational complexity theory","author":"Condon A.","year":"1990","unstructured":"Condon, A. On Algorithms for Simple Stochastic Games. Advances in computational complexity theory (1990)."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_79"},{"key":"e_1_3_2_1_16_1","volume-title":"ICALP","author":"Dorfman D.","year":"2019","unstructured":"Dorfman, D., Kaplan, H., and Zwick, U. A faster deterministic exponential time algorithm for energy games and mean payoff games. In ICALP (2019)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768705"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185392"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746558"},{"key":"e_1_3_2_1_20_1","volume-title":"Competitive Markov Decision Processes","author":"Filar J.","year":"1997","unstructured":"Filar, J., and Vrieze, K. Competitive Markov Decision Processes. Springer-Verlag, 1997."},{"volume-title":"A super-polynomial lower bound for the parity game strategy improvement algorithm as we know it. Logic in Computer Science (LICS)","author":"Friedman O.","key":"e_1_3_2_1_21_1","unstructured":"Friedman, O. A super-polynomial lower bound for the parity game strategy improvement algorithm as we know it. Logic in Computer Science (LICS). IEEE, Los Alamitos (to appear, 2009) (2009)."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993675"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802177"},{"key":"e_1_3_2_1_24_1","first-page":"5","article-title":"Cyclic games and an algorithm to find minimax cycle means in directed graphs","volume":"28","author":"Gurvich V. A.","year":"1990","unstructured":"Gurvich, V. A., Karzanov, A. V., and Khachiyan, L. G. Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Comput. Math. Math. Phys. 28, 5 (1990), 85--91.","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432623"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646514.695804"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/070686652"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.37"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1035"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77050-3_37"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.10.1095"},{"key":"e_1_3_2_1_34_1","volume-title":"Theoretical Computer Science","volume":"183","author":"Zielonka W.","year":"1998","unstructured":"Zielonka, W. Infinite games on finitely coloured graphs with applications to automata on infinite trees. In Theoretical Computer Science (1998), vol. 200(1-2), pp. 135--183."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"event":{"name":"LICS '24: 39th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","IEEE Computer Society","EACSL"],"location":"Tallinn Estonia","acronym":"LICS '24"},"container-title":["Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662080","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3661814.3662080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T17:03:58Z","timestamp":1756487038000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662080"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":35,"alternative-id":["10.1145\/3661814.3662080","10.1145\/3661814"],"URL":"https:\/\/doi.org\/10.1145\/3661814.3662080","relation":{},"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}