{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:50Z","timestamp":1760202530052},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540677703"},{"type":"electronic","value":"9783540450474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/10722167_18","type":"book-chapter","created":{"date-parts":[[2006,12,29]],"date-time":"2006-12-29T22:00:33Z","timestamp":1167429633000},"page":"202-215","source":"Crossref","is-referenced-by-count":100,"title":["A Discrete Strategy Improvement Algorithm for Solving Parity Games"],"prefix":"10.1007","author":[{"given":"Jens","family":"V\u00f6ge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Jurdzi\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"18_CR1","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-2), 237\u2013255 (1997)","journal-title":"Theoretical Computer Science"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Buhrke, N., Lescow, H., V\u00f6ge, J.: Strategy construction in infinite games with Streett and Rabin chain winning conditions. In: Margaria, T., Steffen, B. (eds.) TACAS 1996. LNCS, vol.\u00a01055, pp. 27\u201329. Springer, Heidelberg (1996)","DOI":"10.1007\/3-540-61042-1_46"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"A. Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. Information and Computation\u00a096, 203\u2013224 (1992)","journal-title":"Information and Computation"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Condon, A.: On algorithms for simple stochastic games. In: Cai, J.-Y. (ed.) Advances in Computational Complexity Theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a013, pp. 51\u201373. American Mathematical Society (1993)","DOI":"10.1090\/dimacs\/013\/04"},{"issue":"2","key":"18_CR5","doi-asserted-by":"publisher","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. Journal of Game Theory\u00a08(2), 109\u2013113 (1979)","journal-title":"Int. Journal of Game Theory"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1109\/SFCS.1991.185392","volume-title":"Proceedings of 32nd Annual Symposium on Foundations of Computer Science","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy (Extended abstract). In: Proceedings of 32nd Annual Symposium on Foundations of Computer Science, pp. 368\u2013377. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"18_CR7","doi-asserted-by":"crossref","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. Springer, Heidelberg (1993)","DOI":"10.1007\/3-540-56922-7_32"},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1287\/mnsc.12.5.359","volume":"12","author":"A. Hoffman","year":"1966","unstructured":"Hoffman, A., Karp, R.: On nonterminating stochastic games. Management Science\u00a012, 359\u2013370 (1966)","journal-title":"Management Science"},{"issue":"3","key":"18_CR9","doi-asserted-by":"crossref","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 \u2229 co-UP. Information Processing Letters\u00a068(3), 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"18_CR10","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":"2","key":"18_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. Annals of Pure and Applied Logic\u00a065(2), 149\u2013184 (1993)","journal-title":"Annals of Pure and Applied Logic"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1137\/0212022","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Towards a genuinely polynomial algorithm for linear programming. SIAM Journal on Computing\u00a012, 347\u2013353 (1983)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"18_CR13","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1287\/ijoc.6.2.188","volume":"6","author":"M. Melekopoglou","year":"1994","unstructured":"Melekopoglou, M., Condon, A.: On the complexity of the policy improvement algorithm for stochastic games. ORSA (Op. Res. Soc. of America) Journal of Computing\u00a06(2), 188\u2013192 (1994)","journal-title":"ORSA (Op. Res. Soc. of America) Journal of Computing"},{"key":"18_CR14","unstructured":"Mostowski, A.W.: Games with forbidden positions. Technical Report 78, University of Gda\u0144sk (1991)"},{"key":"18_CR15","unstructured":"Puri, A.: Theory of Hybrid Systems and Discrete Event Systems. PhD thesis, Electronics Research Laboratory, College of Engineering, University of California, Berkeley, Memorandum No. UCB\/ERL M95\/113 (December 1995)"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Schmitz, D., V\u00f6ge, J.: Implementation of a strategy improvement algorithm for finite-state parity games (April 2000) ( manuscipt, unpublished)","DOI":"10.1007\/3-540-44674-5_22"},{"issue":"6","key":"18_CR17","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0020-0190(96)00130-5","volume":"59","author":"H. Seidl","year":"1996","unstructured":"Seidl, H.: Fast and simple nested fixpoints. Information Processing Letters\u00a059(6), 303\u2013308 (1996)","journal-title":"Information Processing Letters"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"CONCUR \u201995 Concurrency Theory","author":"C. Stirling","year":"1995","unstructured":"Stirling, C.: Local model checking games (Extended abstract). In: Lee, I., Smolka, S.A. (eds.) CONCUR 1995. LNCS, vol.\u00a0962, pp. 1\u201311. Springer, Heidelberg (1995)"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"V\u00f6ge, J., Jurdzi\u0144ski, M.: A discrete strategy improvement algorithm for solving parity games. Aachener Informatik-Berichte 2000-2, RWTH Aachen, Fachgruppe Informatik, 52056 Aachen, Germany (February 2000)","DOI":"10.7146\/brics.v7i48.20215"},{"key":"18_CR20","doi-asserted-by":"crossref","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":"18_CR21","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.: The complexity of mean payoff games on graphs. Theoretical Computer Science\u00a0158, 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10722167_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T03:15:24Z","timestamp":1683688524000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10722167_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677703","9783540450474"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/10722167_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2000]]}}}