{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T02:22:41Z","timestamp":1767666161482,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,7,12]],"date-time":"2016-07-12T00:00:00Z","timestamp":1468281600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["601148","601148"],"award-info":[{"award-number":["601148","601148"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00236-016-0276-z","type":"journal-article","created":{"date-parts":[[2016,7,12]],"date-time":"2016-07-12T16:56:27Z","timestamp":1468342587000},"page":"85-125","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games"],"prefix":"10.1007","volume":"54","author":[{"given":"Thomas","family":"Brihaye","sequence":"first","affiliation":[]},{"given":"Gilles","family":"Geeraerts","sequence":"additional","affiliation":[]},{"given":"Axel","family":"Haddad","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4717-9955","authenticated-orcid":false,"given":"Benjamin","family":"Monmege","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,12]]},"reference":[{"key":"276_CR1","doi-asserted-by":"crossref","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.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discret. Appl. Math. 155, 210\u2013229 (2007)","journal-title":"Discret. Appl. Math."},{"key":"276_CR2","doi-asserted-by":"crossref","unstructured":"Brihaye, T., De\u00a0Pril, J., Schewe., S.: Multiplayer cost games with simple nash equilibria. In: Proceedings of the International Symposium on Logical Foundations of Computer Science (LFCS\u201913). Lecture Notes in Computer Science, vol. 7734, pp. 59\u201373. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-35722-0_5"},{"key":"276_CR3","doi-asserted-by":"publisher","unstructured":"Brihaye, T., Geeraerts, G., Krishna, S.N., Manasa, L., Monmege, B., Trivedi, A.:Adding negative prices to priced timed games. In: Proceedings of the 25th International Conference on Concurrency Theory (CONCUR\u201914). Lecture Notes in Computer Science, vol. 8704, pp. 560\u2013575. Springer, Berlin (2014). doi: 10.1007\/978-3-662-44584-63_8","DOI":"10.1007\/978-3-662-44584-63_8"},{"key":"276_CR4","unstructured":"Brihaye, T., Geeraerts, G., Haddad, A., Lefaucheux, E., Monmege, B.: Simple priced timed games are not that simple. In: Proceedings of the 35th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201915), Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, LIPIcs (2015)"},{"key":"276_CR5","unstructured":"Brihaye, T., Geeraerts, G., Haddad, A., Monmege, B.: To reach or not to reach? Efficient algorithms for total-payoff games. In: Proceedings of the 26th International Conference on Concurrency Theory (CONCUR \u201915), Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, LIPIcs, vol. 42, pp. 297\u2013310 (2015)"},{"issue":"2","key":"276_CR6","doi-asserted-by":"crossref","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.F.: Faster algorithms for mean-payoff games. Form. Methods Syst. Des. 38(2), 97\u2013118 (2011)","journal-title":"Form. Methods Syst. Des."},{"issue":"1","key":"276_CR7","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s10703-013-0183-7","volume":"43","author":"T Chen","year":"2013","unstructured":"Chen, T., Forejt, V., Kwiatkowska, M., Parker, D., Simaitis, A.: Automatic verification of competitive stochastic systems. Form. Methods Syst. Des. 43(1), 61\u201392 (2013)","journal-title":"Form. Methods Syst. Des."},{"key":"276_CR8","doi-asserted-by":"publisher","unstructured":"Comin, C., Rizzi, R.: Improved Pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games. Algorithmica (2016). doi: 10.1007\/s00453-016-0123-1","DOI":"10.1007\/s00453-016-0123-1"},{"issue":"2","key":"276_CR9","doi-asserted-by":"crossref","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(2), 109\u2013113 (1979)","journal-title":"Int. J. Game Theory"},{"key":"276_CR10","doi-asserted-by":"crossref","unstructured":"Filiot, E., Gentilini, R., Raskin, J.F.: Quantitative languages defined by functional automata. In: Proceedings of the 23rd International Conference on Concurrency theory (CONCUR \u201912). Lecture Notes in Computer Science, vol. 7454, pp. 132\u2013146. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32940-1_11"},{"key":"276_CR11","doi-asserted-by":"crossref","unstructured":"Gawlitza, T.M., Seidl, H.: Games through nested fixpoints. In: Proceedings of the 21st International Conference on Computer Aided Verification (CAV \u201909). Lecture Notes in Computer Science, vol. 5643, pp. 291\u2013305. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-02658-4_24"},{"key":"276_CR12","doi-asserted-by":"crossref","unstructured":"Gimbert, H., Zielonka, W.: When can you play positionally? In: Proceedings of the 29th International Conference on Mathematical Foundations of Computer Science (MFCS \u201904). Lecture Notes in Computer Science, vol. 3153, pp. 686\u2013698. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-28629-5_53"},{"key":"276_CR13","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/s00224-007-9025-6","volume":"43","author":"L Khachiyan","year":"2008","unstructured":"Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Rudolf, G., Zhao, J.: On short paths interdiction problems: total and node-wise limited interdiction. Theory Comput. Syst. 43, 204\u2013233 (2008)","journal-title":"Theory Comput. Syst."},{"key":"276_CR14","doi-asserted-by":"crossref","unstructured":"Klimo\u0161, M., Larsen, K.G., \u0160tefa\u0148\u00e1k, F., Thaarup, J.: Nash equilibria in concurrent priced games. In: Proceedings of the 6th International Conference on Language and Automata Theory and Applications (LATA\u201912). Lecture Notes in Computer Science, vol. 7183, pp. 363\u2013376. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-28332-1_31"},{"issue":"2","key":"276_CR15","doi-asserted-by":"crossref","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."},{"key":"276_CR16","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes","author":"ML Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes. Wiley, New York (1994)"},{"key":"276_CR17","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1214\/aoms\/1177699369","volume":"37","author":"RE Strauch","year":"1966","unstructured":"Strauch, R.E.: Negative dynamic programming. Ann. Math. Stat. 37, 871\u2013890 (1966)","journal-title":"Ann. Math. Stat."},{"issue":"2","key":"276_CR18","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"276_CR19","doi-asserted-by":"crossref","unstructured":"Thomas, W.: On the synthesis of strategies in infinite games. In: Symposium on Theoretical Aspects of Computer Science (STACS \u201995). Lecture Notes in Computer Science, vol. 900, pp. 1\u201313. Springer, Berlin (1995)","DOI":"10.1007\/3-540-59042-0_57"},{"issue":"2","key":"276_CR20","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF01732644","volume":"9","author":"F Thuijsman","year":"1987","unstructured":"Thuijsman, F., Vrieze, O.J.: The bad match: a total reward stochastic game. Oper. Res. Spektrum 9(2), 93\u201399 (1987)","journal-title":"Oper. Res. Spektrum"},{"key":"276_CR21","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.S.: The complexity of mean payoff games. Theor. Comput. Sci. 158, 343\u2013359 (1996)","journal-title":"Theor. Comput. Sci."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0276-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-016-0276-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0276-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0276-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,10]],"date-time":"2019-09-10T22:21:06Z","timestamp":1568154066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-016-0276-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["276"],"URL":"https:\/\/doi.org\/10.1007\/s00236-016-0276-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2016,7,12]]}}}