{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T01:40:01Z","timestamp":1750556401360,"version":"3.41.0"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319633893"},{"type":"electronic","value":"9783319633909"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-63390-9_8","type":"book-chapter","created":{"date-parts":[[2017,7,12]],"date-time":"2017-07-12T08:53:50Z","timestamp":1499849630000},"page":"137-154","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Efficient Parallel Strategy Improvement for Parity Games"],"prefix":"10.1007","author":[{"given":"John","family":"Fearnley","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,13]]},"reference":[{"issue":"5","key":"8_CR1","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1287\/mnsc.12.5.359","volume":"12","author":"AJ Hoffman","year":"1966","unstructured":"Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Manag. Sci. 12(5), 359\u2013370 (1966)","journal-title":"Manag. Sci."},{"issue":"2","key":"8_CR2","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.G.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discret. Appl. Math. 155(2), 210\u2013229 (2007)","journal-title":"Discret. Appl. Math."},{"unstructured":"Cochet-Terrasson, J., Gaubert, S.: Policy iteration algorithm for shortest path problems. Technical report (2000)","key":"8_CR3"},{"issue":"3","key":"8_CR4","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","volume":"81","author":"R Cole","year":"1989","unstructured":"Cole, R., Vishkin, U.: Faster optimal parallel prefix sums and list ranking. Inf. Comput. 81(3), 334\u2013352 (1989)","journal-title":"Inf. Comput."},{"unstructured":"Condon, A.: On algorithms for simple stochastic games. In: Proceedings of a DIMACS Workshop, Advances in Computational Complexity Theory, pp. 51\u201372 (1990)","key":"8_CR5"},{"doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy. In: Proceedings of FOCS, pp. 368\u2013377 (1991)","key":"8_CR6","DOI":"10.1109\/SFCS.1991.185392"},{"key":"8_CR7","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":"EA Emerson","year":"1993","unstructured":"Emerson, E.A., Jutla, C.S., Sistla, A.P.: On model-checking for fragments of $$\\mu $$-calculus. In: Courcoubetis, C. (ed.) CAV 1993. LNCS, vol. 697, pp. 385\u2013396. Springer, Heidelberg (1993). doi:10.1007\/3-540-56922-7_32"},{"doi-asserted-by":"crossref","unstructured":"Fearnley, J., Savani, R.: The complexity of all-switches strategy improvement. In: Proceedings of SODA, pp. 130\u2013139 (2016)","key":"8_CR8","DOI":"10.1137\/1.9781611974331.ch10"},{"doi-asserted-by":"crossref","unstructured":"Friedmann, O.: An exponential lower bound for the latest deterministic strategy iteration algorithms. Log. Methods Comput. Sci. 7(3) (2011). Paper 23. http:\/\/www.lmcs-online.org\/ojs\/viewarticle.php?id=779&layout=abstract","key":"8_CR9","DOI":"10.2168\/LMCS-7(3:23)2011"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-04761-9_15","volume-title":"Automated Technology for Verification and Analysis","author":"O Friedmann","year":"2009","unstructured":"Friedmann, O., Lange, M.: Solving parity games in practice. In: Liu, Z., Ravn, A.P. (eds.) ATVA 2009. LNCS, vol. 5799, pp. 182\u2013196. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-04761-9_15"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","volume-title":"Automata Logics, and Infinite Games: A Guide to Current Research","year":"2002","unstructured":"Gr\u00e4del, E., Thomas, W., Wilke, T. (eds.): Automata Logics, and Infinite Games: A Guide to Current Research. LNCS, vol. 2500. Springer, Heidelberg (2002)"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-48518-X_3","volume-title":"Algorithm Engineering and Experimentation","author":"DR Helman","year":"1999","unstructured":"Helman, D.R., J\u00e1J\u00e1, J.: Designing practical efficient algorithms for symmetric multiprocessors. In: Goodrich, M.T., McGeoch, C.C. (eds.) ALENEX 1999. LNCS, vol. 1619, pp. 37\u201356. Springer, Heidelberg (1999). doi:10.1007\/3-540-48518-X_3"},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-319-02444-8_34","volume-title":"Automated Technology for Verification and Analysis","author":"P Hoffmann","year":"2013","unstructured":"Hoffmann, P., Luttenberger, M.: Solving parity games on the GPU. In: Hung, D., Ogawa, M. (eds.) ATVA 2013. LNCS, vol. 8172, pp. 455\u2013459. Springer, Cham (2013). doi:10.1007\/978-3-319-02444-8_34"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/978-3-642-34188-5_13","volume-title":"Hardware and Software: Verification and Testing","author":"M Huth","year":"2012","unstructured":"Huth, M., Kuo, J.H.-P., Piterman, N.: Concurrent small progress measures. In: Eder, K., Louren\u00e7o, J., Shehory, O. (eds.) HVC 2011. LNCS, vol. 7261, pp. 130\u2013144. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-34188-5_13"},{"issue":"3","key":"8_CR15","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 $$\\cap $$ co-UP. Inf. Process. Lett. 68(3), 119\u2013124 (1998)","journal-title":"Inf. Process. Lett."},{"key":"8_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. 1770, pp. 290\u2013301. Springer, Heidelberg (2000). doi:10.1007\/3-540-46541-3_24"},{"unstructured":"Kandziora, J.: Playing parity games on the playstation 3. In: Twente Student Conference (2009)","key":"8_CR17"},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-319-24644-4_9","volume-title":"Fundamentals of Software Engineering","author":"JJA Keiren","year":"2015","unstructured":"Keiren, J.J.A.: Benchmarks for parity games. In: Dastani, M., Sirjani, M. (eds.) FSEN 2015. LNCS, vol. 9392, pp. 127\u2013142. Springer, Cham (2015). doi:10.1007\/978-3-319-24644-4_9"},{"issue":"4","key":"8_CR19","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"RE Ladner","year":"1980","unstructured":"Ladner, R.E., Fischer, M.J.: Parallel prefix computation. J. ACM 27(4), 831\u2013838 (1980)","journal-title":"J. ACM"},{"unstructured":"Luttenberger, M.: Strategy iteration using non-deterministic strategies for solving parity games. CoRR, abs\/0806.2923 (2008)","key":"8_CR20"},{"issue":"4\u20135","key":"8_CR21","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16(4\u20135), 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"8_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-319-46520-3_17","volume-title":"Automated Technology for Verification and Analysis","author":"PJ Meyer","year":"2016","unstructured":"Meyer, P.J., Luttenberger, M.: Solving mean-payoff games on the GPU. In: Artho, C., Legay, A., Peled, D. (eds.) ATVA 2016. LNCS, vol. 9938, pp. 262\u2013267. Springer, Cham (2016). doi:10.1007\/978-3-319-46520-3_17"},{"unstructured":"Mostowski, A.W.: Games with forbidden positions. Technical report 78, University of Gda\u0144sk (1991)","key":"8_CR23"},{"unstructured":"Puri, A.: Theory of hybrid systems and discrete event systems. Ph.D. thesis, University of California, Berkeley (1995)","key":"8_CR24"},{"key":"8_CR25","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"ML Puterman","year":"2005","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (2005)"},{"key":"8_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","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. 5213, pp. 369\u2013384. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-87531-4_27"},{"key":"8_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-60218-6_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. 962, pp. 1\u201311. Springer, Heidelberg (1995). doi:10.1007\/3-540-60218-6_1"},{"issue":"2","key":"8_CR28","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-540-69149-5_2","volume":"220","author":"J van de Pol","year":"2008","unstructured":"van de Pol, J., Weber, M.: A multi-core solver for parity games. Electr. Notes Theoret. Comput. Sci. 220(2), 19\u201334 (2008)","journal-title":"Electr. Notes Theoret. Comput. Sci."},{"unstructured":"van der Berg, F.: Solving parity games on the playstation 3. In: Twente Student Conference (2010)","key":"8_CR29"},{"key":"8_CR30","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. 1855, pp. 202\u2013215. Springer, Heidelberg (2000). doi:10.1007\/10722167_18"},{"issue":"4","key":"8_CR31","doi-asserted-by":"publisher","first-page":"1250012","DOI":"10.1142\/S0129626412500120","volume":"22","author":"Z Wei","year":"2012","unstructured":"Wei, Z., J\u00e1J\u00e1, J.: Optimization of linked list prefix computations on multithreaded GPUs using CUDA. Parallel Process. Lett. 22(4), 1250012 (2012)","journal-title":"Parallel Process. Lett."},{"key":"8_CR32","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. Theoret. Comput. Sci. 200, 135\u2013183 (1998)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"8_CR33","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. Theoret. Comput. Sci. 158(1\u20132), 343\u2013359 (1996)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-63390-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T01:06:58Z","timestamp":1750554418000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-63390-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319633893","9783319633909"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-63390-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"13 July 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CAV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computer Aided Verification","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Heidelberg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 July 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 July 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cav2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cavconference.org\/2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}