{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:20:48Z","timestamp":1776316848556,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,12,8]],"date-time":"2010-12-08T00:00:00Z","timestamp":1291766400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form Methods Syst Des"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s10703-010-0105-x","type":"journal-article","created":{"date-parts":[[2010,12,7]],"date-time":"2010-12-07T13:23:02Z","timestamp":1291728182000},"page":"97-118","source":"Crossref","is-referenced-by-count":88,"title":["Faster algorithms for mean-payoff games"],"prefix":"10.1007","volume":"38","author":[{"given":"L.","family":"Brim","sequence":"first","affiliation":[]},{"given":"J.","family":"Chaloupka","sequence":"additional","affiliation":[]},{"given":"L.","family":"Doyen","sequence":"additional","affiliation":[]},{"given":"R.","family":"Gentilini","sequence":"additional","affiliation":[]},{"given":"J. F.","family":"Raskin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,12,8]]},"reference":[{"key":"105_CR1","unstructured":"Andersson D, Vorobyov S (2006) Fast algorithms for monotonic discounted linear programs with two variables per inequality. Preprint NI06019-LAA, Isaac Newton Institute for Mathematical Sciences, Cambridge, UK"},{"key":"105_CR2","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/j.dam.2006.04.029","volume":"155","author":"H Bjorklund","year":"2007","unstructured":"Bjorklund H, Vorobyov S (2007) A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Appl Math 155:210\u2013229","journal-title":"Discrete Appl Math"},{"key":"105_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-540-85778-5_4","volume-title":"Proc of FORMATS: formal modeling and analysis of timed systems","author":"P Bouyer","year":"2008","unstructured":"Bouyer P, Fahrenberg U, Larsen KG, Markey N, Srba J (2008) Infinite runs in weighted timed automata with energy constraints. In: Proc of FORMATS: formal modeling and analysis of timed systems. LNCS, vol 5215. Springer, Berlin, pp 33\u201347"},{"key":"105_CR4","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-540-45212-6_9","volume-title":"Proc of EMSOFT: embedded software","author":"A Chakrabarti","year":"2003","unstructured":"Chakrabarti A, de Alfaro L, Henzinger TA, Stoelinga M (2003) Resource interfaces. In: Proc of EMSOFT: embedded software. LNCS, vol 2855. Springer, Berlin, pp 117\u2013133"},{"key":"105_CR5","unstructured":"Chaloupka J, Brim L (2009) Faster algorithm for mean-payoff games. In: Proc of the 5th docoral workshop on mathematical and engineering methods in computer science (MEMICS \u201909). Novpress, pp 45\u201353"},{"key":"105_CR6","series-title":"DIMACS series in discrete mathematics and theoretical computer science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1090\/dimacs\/013\/04","volume-title":"Advances in computational complexity theory","author":"A Condon","year":"1993","unstructured":"Condon A (1993) On algorithms for simple stochastic games. In: Advances in computational complexity theory. DIMACS series in discrete mathematics and theoretical computer science, vol 13. American Mathematical Society, Providence, pp 51\u201373"},{"key":"105_CR7","volume-title":"Proc. of Valuetools: International conference on performance evaluation methodologies and tools","author":"V Dhingra","year":"2006","unstructured":"Dhingra V, Gaubert S (2006) How to solve large scale deterministic games with mean payoff by policy iteration. In: Proc. of Valuetools: International conference on performance evaluation methodologies and tools. ACM, New York"},{"key":"105_CR8","unstructured":"Doyen L, Gentilini R, Raskin J-F (2009) Faster pseudopolynomial algorithms for meanpayoff games Technical Report 2009.120. Universite Libre de Bruxelles (ULB), Bruxelles, Belgium"},{"key":"105_CR9","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht A, Mycielski J (1979) Positional strategies for mean-payoff games. Int J Game Theory 8:109\u2013113","journal-title":"Int J Game Theory"},{"key":"105_CR10","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/3-540-56922-7_32","volume-title":"Proc of CAV: computer aided verification","author":"EA Emerson","year":"1993","unstructured":"Emerson EA, Jutla C, Sistal AP (1993) On model checking for fragments of the \u03bc-calculus. In: Proc of CAV: computer aided verification. LNCS, vol 697. Springer, Berlin, pp 385\u2013396"},{"key":"105_CR11","first-page":"60","volume-title":"Proc of STOC: symposium on theory of computing","author":"Y Gurevich","year":"1982","unstructured":"Gurevich Y, Harrington L (1982) Trees, automata, and games. In: Proc of STOC: symposium on theory of computing. ACM, New York, pp 60\u201365"},{"issue":"28","key":"105_CR12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"5","author":"VA Gurvich","year":"1988","unstructured":"Gurvich VA, Karzanov AV, Kachiyan LG (1988) Cyclic games and an algorithm to find minmax cycle means in directed graphs. USSR Comput Math Math Phys 5(28):85\u201391","journal-title":"USSR Comput Math Math Phys"},{"issue":"3","key":"105_CR13","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M Jurdzinski","year":"1998","unstructured":"Jurdzinski M (1998) Deciding the winner in parity games is in UP \u2229 coUP. Inf Process Lett 68(3): 119\u2013124","journal-title":"Inf Process Lett"},{"key":"105_CR14","series-title":"LNCS","first-page":"290","volume-title":"Proceedings of STACS: theoretical aspects of computer science","author":"M Jurdzinski","year":"2000","unstructured":"Jurdzinski M (2000) Small progress measures for solving parity games. In: Proceedings of STACS: theoretical aspects of computer science. LNCS, vol 1770. Springer, Berlin, pp 290\u2013301"},{"key":"105_CR15","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01580616","volume":"60","author":"AV Karzanov","year":"1993","unstructured":"Karzanov AV, Lebedev VN (1993) Cyclical games with prohibitions. Math Program 60:277\u2013293","journal-title":"Math Program"},{"key":"105_CR16","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D Kozen","year":"1983","unstructured":"Kozen D (1983) Results on the propositional mu-calculus. Theor Comput Sci 27:333\u2013354","journal-title":"Theor Comput Sci"},{"issue":"3","key":"105_CR17","doi-asserted-by":"crossref","first-page":"4967","DOI":"10.1007\/s10958-007-0331-y","volume":"145","author":"Y Lifshits","year":"2007","unstructured":"Lifshits Y, Pavlov D (2007) Potential theory for mean payoff games. J Math Sci 145(3):4967\u20134974","journal-title":"J Math Sci"},{"key":"105_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0931-7","volume-title":"The temporal logic of reactive and concurrent programs","author":"Z Manna","year":"1992","unstructured":"Manna Z, Pnueli A (1992) The temporal logic of reactive and concurrent programs. Springer, Berlin"},{"key":"105_CR19","volume-title":"Computational complexity","author":"CM Papadimitriou","year":"1994","unstructured":"Papadimitriou CM (1994) Computational complexity. Addison-Wesley, Reading"},{"issue":"24","key":"105_CR20","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1287\/moor.24.4.817","volume":"4","author":"N Pisaruk","year":"1999","unstructured":"Pisaruk N (1999) Mean cost cyclical games. Math Oper Res 4(24):817\u2013828","journal-title":"Math Oper Res"},{"key":"105_CR21","series-title":"LNCS","first-page":"675","volume-title":"Proceedings of MFCS: mathematical foundations of computer science","author":"S Schewe","year":"2009","unstructured":"Schewe S (2009) From parity and payoff games to linear programming. In: Proceedings of MFCS: mathematical foundations of computer science. LNCS, vol 5734. Springer, Berlin, pp 675\u2013686"},{"key":"105_CR22","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/3-540-61474-5_58","volume-title":"Proceedings of CAV: computer aided verification","author":"I Walukiewicz","year":"1996","unstructured":"Walukiewicz I (1996) Pushdown processes: Games and model checking. In: Proceedings of CAV: computer aided verification. LNCS, vol 1102. Springer, Berlin, pp 62\u201374"},{"key":"105_CR23","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 (1996) The complexity of mean payoff games on graphs. Theor Comput Sci 158:343\u2013359","journal-title":"Theor Comput Sci"}],"container-title":["Formal Methods in System Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10703-010-0105-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10703-010-0105-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10703-010-0105-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T21:47:33Z","timestamp":1559857653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10703-010-0105-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,8]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["105"],"URL":"https:\/\/doi.org\/10.1007\/s10703-010-0105-x","relation":{},"ISSN":["0925-9856","1572-8102"],"issn-type":[{"value":"0925-9856","type":"print"},{"value":"1572-8102","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,8]]}}}