{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:46:49Z","timestamp":1764402409065,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540875307"},{"type":"electronic","value":"9783540875314"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87531-4_27","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T08:40:53Z","timestamp":1220085653000},"page":"369-384","source":"Crossref","is-referenced-by-count":43,"title":["An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games"],"prefix":"10.1007","author":[{"given":"Sven","family":"Schewe","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D. Kozen","year":"1983","unstructured":"Kozen, D.: Results on the propositional \u03bc-calculus. Theor. Comput. Sci.\u00a027, 333\u2013354 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model-checking for fragments of \u03bc-calculus. In: Proc. CAV, pp. 385\u2013396 (1993)","DOI":"10.1007\/3-540-56922-7_32"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Wilke, T.: Alternating tree automata, parity games, and modal \u03bc-calculus. Bull. Soc. Math. Belg.\u00a08(2) (2001)","DOI":"10.36045\/bbms\/1102714178"},{"key":"27_CR4","first-page":"279","volume-title":"Proc. LICS","author":"L. de Alfaro","year":"2001","unstructured":"de Alfaro, L., Henzinger, T.A., Majumdar, R.: From verification to control: Dynamic programs for omega-regular objectives. In: Proc. LICS, pp. 279\u2013290. IEEE Computer Society Press, Los Alamitos (2001)"},{"issue":"5","key":"27_CR5","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1145\/585265.585270","volume":"49","author":"R. Alur","year":"2002","unstructured":"Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. Journal of the ACM\u00a049(5), 672\u2013713 (2002)","journal-title":"Journal of the ACM"},{"key":"27_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/BFb0055090","volume-title":"Automata, Languages and Programming","author":"M.Y. Vardi","year":"1998","unstructured":"Vardi, M.Y.: Reasoning about the past with two-way automata. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 628\u2013641. Springer, Heidelberg (1998)"},{"key":"27_CR7","first-page":"591","volume-title":"Proc. CSL","author":"S. Schewe","year":"2006","unstructured":"Schewe, S., Finkbeiner, B.: The alternating-time \u03bc-calculus and automata over concurrent game structures. In: Proc. CSL, pp. 591\u2013605. Springer, Heidelberg (2006)"},{"key":"27_CR8","first-page":"255","volume-title":"Proc. LICS","author":"N. Piterman","year":"2006","unstructured":"Piterman, N.: From nondeterministic B\u00fcchi and Streett automata to deterministic parity automata. In: Proc. LICS, pp. 255\u2013264. IEEE Computer Society, Los Alamitos (2006)"},{"key":"27_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-540-71410-1_10","volume-title":"Logic-Based Program Synthesis and Transformation","author":"S. Schewe","year":"2007","unstructured":"Schewe, S., Finkbeiner, B.: Synthesis of asynchronous systems. In: Puebla, G. (ed.) LOPSTR 2006. LNCS, vol.\u00a04407, pp. 127\u2013142. Springer, Heidelberg (2007)"},{"key":"27_CR10","first-page":"267","volume-title":"Proc. LICS","author":"E.A. Emerson","year":"1986","unstructured":"Emerson, E.A., Lei, C.: Efcient model checking in fragments of the propositional \u03bc-calculus. In: Proc. LICS, pp. 267\u2013278. IEEE Computer Society Press, Los Alamitos (1986)"},{"key":"27_CR11","first-page":"368","volume-title":"Proc. FOCS","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, \u03bc-calculus and determinacy. In: Proc. FOCS, pp. 368\u2013377. IEEE Computer Society Press, Los Alamitos (1991)"},{"issue":"2","key":"27_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0168-0072(93)90036-D","volume":"65","author":"R. McNaughton","year":"1993","unstructured":"McNaughton, R.: Infinite games played on finite graphs. Ann. Pure Appl. Logic\u00a065(2), 149\u2013184 (1993)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1\u20132","key":"27_CR13","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.S.: The complexity of mean payoff games on graphs. Theoretical Computer Science\u00a0158(1\u20132), 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"27_CR14","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(96)00228-9","volume":"178","author":"A. Browne","year":"1997","unstructured":"Browne, A., Clarke, E.M., Jha, S., Long, D.E., Marrero, W.: An improved algorithm for the evaluation of fixpoint expressions. Theoretical Computer Science\u00a0178(1\u20132), 237\u2013255 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"27_CR15","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.\u00a0200(1-2), 135\u2013183 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/3-540-46541-3_24","volume-title":"STACS 2000","author":"M. Jurdzi\u0144ski","year":"2000","unstructured":"Jurdzi\u0144ski, M.: Small progress measures for solving parity games. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 290\u2013301. Springer, Heidelberg (2000)"},{"issue":"1","key":"27_CR17","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1006\/inco.1995.1035","volume":"117","author":"W. Ludwig","year":"1995","unstructured":"Ludwig, W.: A subexponential randomized algorithm for the simple stochastic game problem. Inf. Comput.\u00a0117(1), 151\u2013155 (1995)","journal-title":"Inf. Comput."},{"key":"27_CR18","unstructured":"Puri, A.: Theory of hybrid systems and discrete event systems. PhD thesis, Computer Science Department, University of California, Berkeley (1995)"},{"key":"27_CR19","first-page":"202","volume-title":"Proc. CAV","author":"J. V\u00f6ge","year":"2000","unstructured":"V\u00f6ge, J., Jurdzi\u0144ski, M.: A discrete strategy improvement algorithm for solving parity games. In: Proc. CAV, pp. 202\u2013215. Springer, Heidelberg (2000)"},{"issue":"2","key":"27_CR20","doi-asserted-by":"publisher","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. Discrete Appl. Math.\u00a0155(2), 210\u2013229 (2007)","journal-title":"Discrete Appl. Math."},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/978-3-540-45069-6_7","volume-title":"Computer Aided Verification","author":"J. Obdr\u017e\u00e1lek","year":"2003","unstructured":"Obdr\u017e\u00e1lek, J.: Fast mu-calculus model checking when tree-width is bounded. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol.\u00a02725, pp. 80\u201392. Springer, Heidelberg (2003)"},{"key":"27_CR22","unstructured":"Lange, M.: Solving parity games by a reduction to SAT. In: Proc. Int. Workshop on Games in Design and Verification (2005)"},{"key":"27_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/11672142_43","volume-title":"STACS 2006","author":"D. Berwanger","year":"2006","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: Dag-width and parity games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 524\u2013536. Springer, Heidelberg (2006)"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. In: Proc. SODA, pp. 117\u2013123. ACM\/SIAM (2006)","DOI":"10.1145\/1109557.1109571"},{"key":"27_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-540-77050-3_37","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science","author":"S. Schewe","year":"2007","unstructured":"Schewe, S.: Solving parity games in big steps. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol.\u00a04855, pp. 449\u2013460. Springer, Heidelberg (2007)"},{"key":"27_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/3-540-48686-0_4","volume-title":"Computing and Combinatorics","author":"T. Takaoka","year":"1999","unstructured":"Takaoka, T.: Theory of 2-3 heaps. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol.\u00a01627, pp. 41\u201350. Springer, Heidelberg (1999)"},{"key":"27_CR27","unstructured":"Schewe, S.: Synthesis of Distributed Systems. PhD thesis, Saarland University, Saarbr\u00fccken, Germany (2008)"},{"issue":"3","key":"27_CR28","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02591902","volume":"27","author":"S. Smale","year":"1983","unstructured":"Smale, S.: On the average number of steps of the simplex method of linear programming. Mathematical Programming\u00a027(3), 241\u2013262 (1983)","journal-title":"Mathematical Programming"},{"key":"27_CR29","unstructured":"Klee, F., Minty, G.J.: How good is the simplex algorithm? Inequalities III, pp. 159\u2013175 (1972)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87531-4_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T05:14:10Z","timestamp":1715058850000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87531-4_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540875307","9783540875314"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87531-4_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}