{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:46:58Z","timestamp":1725536818920},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_57","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"675-686","source":"Crossref","is-referenced-by-count":6,"title":["From Parity and Payoff Games to Linear Programming"],"prefix":"10.1007","author":[{"given":"Sven","family":"Schewe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"57_CR1","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, 241\u2013262 (1983)","journal-title":"Mathematical Programming"},{"key":"57_CR2","unstructured":"Klee, F., Minty, G.J.: How good is the simplex algorithm? Inequalities III, 159\u2013175 (1972)"},{"key":"57_CR3","first-page":"1093","volume":"244","author":"L.G. Khachian","year":"1979","unstructured":"Khachian, L.G.: A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR\u00a0244, 1093\u20131096 (1979)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"57_CR4","first-page":"302","volume-title":"Proceedings of STOC 1984","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of STOC 1984, pp. 302\u2013311. ACM Press, New York (1984)"},{"key":"57_CR5","first-page":"502","volume":"18","author":"B. G\u00e4rtner","year":"1994","unstructured":"G\u00e4rtner, B., Henk, M., Ziegler, G.M.: Randomized simplex algorithms on Klee-Minty cubes. Combinatorica\u00a018, 502\u2013510 (1994)","journal-title":"Combinatorica"},{"key":"57_CR6","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM\u00a051, 385\u2013463 (2004)","journal-title":"Journal of the ACM"},{"key":"57_CR7","first-page":"51","volume-title":"Proceedings of STOC 2006","author":"J.A. Kelner","year":"2006","unstructured":"Kelner, J.A., Spielman, D.A.: A randomized polynomial-time simplex algorithm for linear programming. In: Proceedings of STOC 2006, pp. 51\u201360. ACM Press, New York (2006)"},{"key":"57_CR8","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF03025291","volume":"20","author":"S. Smale","year":"1998","unstructured":"Smale, S.: Mathematical problems for the next century. The Mathematical Inteligencer\u00a020, 7\u201315 (1998)","journal-title":"The Mathematical Inteligencer"},{"key":"57_CR9","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. Theoretical Computer Science\u00a027, 333\u2013354 (1983)","journal-title":"Theoretical Computer Science"},{"key":"57_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/3-540-56922-7_32","volume-title":"Computer Aided Verification","author":"E.A. Emerson","year":"1993","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model-checking for fragments of \u03bc-calculus. In: Courcoubetis, C. (ed.) CAV 1993. LNCS, vol.\u00a0697, pp. 385\u2013396. Springer, Heidelberg (1993)"},{"key":"57_CR11","doi-asserted-by":"crossref","unstructured":"Wilke, T.: Alternating tree automata, parity games, and modal \u03bc-calculus. Bulletin of the Belgian Mathematical Society 8 (2001)","DOI":"10.36045\/bbms\/1102714178"},{"key":"57_CR12","first-page":"279","volume-title":"Proceedings of LICS 2001","author":"L. Alfaro de","year":"2001","unstructured":"de Alfaro, L., Henzinger, T.A., Majumdar, R.: From verification to control: Dynamic programs for omega-regular objectives. In: Proceedings of LICS 2001, pp. 279\u2013290. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"57_CR13","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, 672\u2013713 (2002)","journal-title":"Journal of the ACM"},{"key":"57_CR14","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":"57_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/11874683_39","volume-title":"Computer Science Logic","author":"S. Schewe","year":"2006","unstructured":"Schewe, S., Finkbeiner, B.: Satisfiability and finite model property for the alternating-time \u03bc-calculus. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 591\u2013605. Springer, Heidelberg (2006)"},{"key":"57_CR16","doi-asserted-by":"crossref","unstructured":"Piterman, N.: From nondeterministic B\u00fcchi and Streett automata to deterministic parity automata. Journal of Logical Methods in Computer Science\u00a03 (2007)","DOI":"10.2168\/LMCS-3(3:5)2007"},{"key":"57_CR17","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":"2006","unstructured":"Schewe, S., Finkbeiner, B.: Synthesis of asynchronous systems. In: Puebla, G. (ed.) LOPSTR 2006. LNCS, vol.\u00a04407, pp. 127\u2013142. Springer, Heidelberg (2006)"},{"key":"57_CR18","first-page":"267","volume-title":"Proceedings of LICS 1986","author":"E.A. Emerson","year":"1986","unstructured":"Emerson, E.A., Lei, C.: Efficient model checking in fragments of the propositional \u03bc-calculus. In: Proceedings of LICS 1986, pp. 267\u2013278. IEEE Computer Society Press, Los Alamitos (1986)"},{"key":"57_CR19","first-page":"368","volume-title":"Proceedings of FOCS 1991","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, \u03bc-calculus and determinacy. In: Proceedings of FOCS 1991, pp. 368\u2013377. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"57_CR20","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. Annals of Pure and Applied Logic\u00a065, 149\u2013184 (1993)","journal-title":"Annals of Pure and Applied Logic"},{"key":"57_CR21","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, 237\u2013255 (1997)","journal-title":"Theoretical Computer Science"},{"key":"57_CR22","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzi\u0144ski","year":"1998","unstructured":"Jurdzi\u0144ski, M.: Deciding the winner in parity games is in UP\u00a0\u2229\u00a0co-UP. Information Processing Letters\u00a068, 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"57_CR23","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. Theoretical Computer Science\u00a0200, 135\u2013183 (1998)","journal-title":"Theoretical Computer Science"},{"key":"57_CR24","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)"},{"key":"57_CR25","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. Information and Computation\u00a0117, 151\u2013155 (1995)","journal-title":"Information and Computation"},{"key":"57_CR26","unstructured":"Puri, A.: Theory of hybrid systems and discrete event systems. PhD thesis, Computer Science Department, University of California, Berkeley (1995)"},{"key":"57_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/10722167_18","volume-title":"Computer Aided Verification","author":"J. V\u00f6ge","year":"2000","unstructured":"V\u00f6ge, J., Jurdzi\u0144ski, M.: A discrete strategy improvement algorithm for solving parity games. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol.\u00a01855, pp. 202\u2013215. Springer, Heidelberg (2000)"},{"key":"57_CR28","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 Applied Mathematics\u00a0155, 210\u2013229 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"57_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-540-87531-4_27","volume-title":"Computer Science Logic","author":"S. Schewe","year":"2008","unstructured":"Schewe, S.: An optimal strategy improvement algorithm for solving parity and payoff games. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol.\u00a05213, pp. 368\u2013383. Springer, Heidelberg (2008)"},{"key":"57_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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 \u03bc-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":"57_CR31","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":"57_CR32","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":"57_CR33","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1137\/070686652","volume":"38","author":"M. Jurdzi\u0144ski","year":"2008","unstructured":"Jurdzi\u0144ski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. SIAM Journal of Computing\u00a038, 1519\u20131532 (2008)","journal-title":"SIAM Journal of Computing"},{"key":"57_CR34","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, 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"},{"key":"57_CR35","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01768705","volume":"2","author":"A. Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. International Journal of Game Theory\u00a02, 109\u2013113 (1979)","journal-title":"International Journal of Game Theory"},{"key":"57_CR36","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"V.A. Gurvich","year":"1988","unstructured":"Gurvich, V.A., Karzanov, A.V., Khachivan, L.G.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics\u00a028, 85\u201391 (1988)","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"key":"57_CR37","doi-asserted-by":"crossref","unstructured":"Friedmann, O.: A super-polynomial lower bound for the parity game strategy improvement algorithm as we know it. In: Proceedings of LICS (2009)","DOI":"10.1109\/LICS.2009.27"},{"key":"57_CR38","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0167-6377(89)90014-X","volume":"8","author":"N. Megiddo","year":"1989","unstructured":"Megiddo, N., Chandrasekaran, R.: On the \u03b5-perturbation method for avoiding degeneracy. Operations Research Letters\u00a08, 305\u2013308 (1989)","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T14:58:04Z","timestamp":1590073084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}