{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:11Z","timestamp":1760202551976},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770497"},{"type":"electronic","value":"9783540770503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77050-3_37","type":"book-chapter","created":{"date-parts":[[2007,11,26]],"date-time":"2007-11-26T08:39:22Z","timestamp":1196066362000},"page":"449-460","source":"Crossref","is-referenced-by-count":58,"title":["Solving Parity Games in Big Steps"],"prefix":"10.1007","author":[{"given":"Sven","family":"Schewe","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"37_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":"37_CR2","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model-checking for fragments of \u03bc-calculus. In: CAV, pp. 385\u2013396 (1993)","DOI":"10.1007\/3-540-56922-7_32"},{"key":"37_CR3","first-page":"279","volume-title":"Proc. LICS","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: Proc. LICS, June 2001, pp. 279\u2013290. IEEE Computer Society Press, Los Alamitos (2001)"},{"issue":"5","key":"37_CR4","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":"37_CR5","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":"37_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/3-540-63166-6_7","volume-title":"Computer Aided Verification","author":"O. Kupferman","year":"1997","unstructured":"Kupferman, O., Vardi, M.Y.: Module checking revisited. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol.\u00a01254, pp. 36\u201347. Springer, Heidelberg (1997)"},{"key":"37_CR7","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":"37_CR8","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.: The alternating-time \u03bc-calculus and automata over concurrent game structures. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 591\u2013605. Springer, Heidelberg (2006)"},{"key":"37_CR9","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 Press, Los Alamitos (2006)"},{"key":"37_CR10","first-page":"127","volume-title":"LOPSTR 2006","author":"S. Schewe","year":"2006","unstructured":"Schewe, S., FinkbUeiner, B.: Synthesis of asynchronous systems. In: LOPSTR 2006, pp. 127\u2013142. Springer, Heidelberg (2006)"},{"issue":"2","key":"37_CR11","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"},{"key":"37_CR12","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)"},{"issue":"1","key":"37_CR13","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":"37_CR14","unstructured":"Puri, A.: Theory of hybrid systems and discrete event systems. PhD thesis, Computer Science Department, University of California, Berkeley (1995)"},{"issue":"1\u20132","key":"37_CR15","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":"37_CR16","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":"37_CR17","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."},{"issue":"3","key":"37_CR18","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(3), 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"37_CR19","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":"37_CR20","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":"37_CR21","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 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":"37_CR22","unstructured":"Lange, M.: Solving parity games by a reduction to SAT. In: Majumdar, R., Jurdziski, M. (eds.) Proc. Int. Workshop on Games in Design and Verification (2005)"},{"key":"37_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","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. 436\u2013524. Springer, Heidelberg (2006)"},{"key":"37_CR24","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. In: Proc. SODA, ACM\/SIAM, pp. 117\u2013123 (2006)","DOI":"10.1145\/1109557.1109571"},{"issue":"2","key":"37_CR25","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."}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77050-3_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:08:48Z","timestamp":1606183728000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77050-3_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770497","9783540770503"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77050-3_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}