{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:59:19Z","timestamp":1764403159316,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031095733"},{"type":"electronic","value":"9783031095740"}],"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.springer.com\/tdm"},{"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.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09574-0_17","type":"book-chapter","created":{"date-parts":[[2022,6,23]],"date-time":"2022-06-23T17:36:07Z","timestamp":1656005767000},"page":"269-288","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The GKK Algorithm is the\u00a0Fastest over\u00a0Simple Mean-Payoff Games"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4685-5253","authenticated-orcid":false,"given":"Pierre","family":"Ohlmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"issue":"3","key":"17_CR1","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2005.07.041","volume":"349","author":"H Bj\u00f6rklund","year":"2005","unstructured":"Bj\u00f6rklund, H., Vorobyov, S.G.: Combinatorial structure and randomized subexponential algorithms for infinite games. Theor. Comput. Sci. 349(3), 347\u2013360 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-540-85778-5_4","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"P Bouyer","year":"2008","unstructured":"Bouyer, P., Fahrenberg, U., Larsen, K.G., Markey, N., Srba, J.: Infinite runs in weighted timed automata with energy constraints. In: Cassez, F., Jard, C. (eds.) FORMATS 2008. LNCS, vol. 5215, pp. 33\u201347. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85778-5_4"},{"issue":"2","key":"17_CR3","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10703-010-0105-x","volume":"38","author":"L Brim","year":"2011","unstructured":"Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.: Faster algorithms for mean-payoff games. Formal Methods Syst. Des. 38(2), 97\u2013118 (2011). https:\/\/doi.org\/10.1007\/s10703-010-0105-x","journal-title":"Formal Methods Syst. Des."},{"doi-asserted-by":"crossref","unstructured":"Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasi-polynomial time. In: STOC, pp. 252\u2013263 (2017)","key":"17_CR4","DOI":"10.1145\/3055399.3055409"},{"issue":"4","key":"17_CR5","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1007\/s00453-016-0123-1","volume":"77","author":"C Comin","year":"2017","unstructured":"Comin, C., Rizzi, R.: Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games. Algorithmica 77(4), 995\u20131021 (2017). https:\/\/doi.org\/10.1007\/s00453-016-0123-1","journal-title":"Algorithmica"},{"unstructured":"Dorfman, D., Kaplan, H., Zwick, U.: A faster deterministic exponential time algorithm for energy games and mean payoff games. In: ICALP, pp. 114:1\u2013114:14 (2019)","key":"17_CR6"},{"key":"17_CR7","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 8, 109\u2013113 (1979). https:\/\/doi.org\/10.1007\/BF01768705","journal-title":"Int. J. Game Theory"},{"unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, $$\\mu $$-calculus and determinacy. In: FOCS, pp. 368\u2013377. IEEE Computer Society (1991)","key":"17_CR8"},{"unstructured":"Fijalkow, N., Gawrychowski, P., Ohlmann, P.: Value iteration using universal graphs and the complexity of mean payoff games. In: MFCS. LIPIcs, vol. 170, pp. 34:1\u201334:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)","key":"17_CR9"},{"issue":"3\u20134","key":"17_CR10","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/BF02020271","volume":"9","author":"T Gallai","year":"1958","unstructured":"Gallai, T.: Maximum-minimum s\u00e4tze \u00fcber graphen. Acta Math. Acad. Sci. Hung. 9(3\u20134), 395\u2013434 (1958)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"17_CR11","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."},{"issue":"2","key":"17_CR12","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."},{"unstructured":"Mostowski, A.W.: Games with forbidden positions. Technical report 78, University of Gdansk (1991)","key":"17_CR13"},{"issue":"4","key":"17_CR14","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1287\/moor.24.4.817","volume":"24","author":"NN Pisaruk","year":"1999","unstructured":"Pisaruk, N.N.: Mean cost cyclical games. Math. Oper. Res. 24(4), 817\u2013828 (1999)","journal-title":"Math. Oper. Res."},{"unstructured":"Puri, A.: Theory of hybrid systems and discrete event systems. Ph.D. thesis, EECS Department, University of California, Berkeley, December 1995","key":"17_CR15"},{"issue":"1\u20132","key":"17_CR16","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."},{"issue":"1\u20132","key":"17_CR17","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1\u20132), 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09574-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T23:03:46Z","timestamp":1656284626000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09574-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031095733","9783031095740"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09574-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"24 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. Petersburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2022\/","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":"21","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":"41% - 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":"7","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)"}}]}}