{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T22:10:06Z","timestamp":1748815806412,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_47","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T08:09:41Z","timestamp":1458547781000},"page":"634-645","source":"Crossref","is-referenced-by-count":2,"title":["New Deterministic Algorithms for Solving Parity Games"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Mnich","sequence":"first","affiliation":[]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[]},{"given":"Clemens","family":"R\u00f6sner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"key":"47_CR1","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. 3884, pp. 524\u2013536. Springer, Heidelberg (2006)"},{"key":"47_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2012.07.010","volume":"463","author":"D Berwanger","year":"2012","unstructured":"Berwanger, D., Gr\u00e4del, E., Kaiser, \u0141., Rabinovich, R.: Entanglement and the complexity of directed graphs. Theoret. Comput. Sci. 463, 2\u201325 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"47_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/3-540-36494-3_58","volume-title":"STACS 2003","author":"H Bj\u00f6rklund","year":"2003","unstructured":"Bj\u00f6rklund, H., Sandberg, S., Vorobyov, S.: A discrete subexponential algorithm for parity games. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 663\u2013674. Springer, Heidelberg (2003)"},{"key":"47_CR4","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy. In: Proceedings of FOCS 1991, pp. 368\u2013377 (1991)","DOI":"10.1109\/SFCS.1991.185392"},{"key":"47_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-642-22993-0_29","volume-title":"Mathematical Foundations of Computer Science 2011","author":"J Fearnley","year":"2011","unstructured":"Fearnley, J., Lachish, O.: Parity games on graphs with medium tree-width. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 303\u2013314. Springer, Heidelberg (2011)"},{"key":"47_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-642-31585-5_20","volume-title":"Automata, Languages, and Programming","author":"J Fearnley","year":"2012","unstructured":"Fearnley, J., Schewe, S.: Time and parallelizability results for parity games with bounded treewidth. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 189\u2013200. Springer, Heidelberg (2012)"},{"key":"47_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-662-48054-0_28","volume-title":"Mathematical Foundations of Computer Science 2015","author":"J Gajarsk\u00fd","year":"2015","unstructured":"Gajarsk\u00fd, J., Lampis, M., Makino, K., Mitsou, V., Ordyniak, S.: Parameterized algorithms for parity games. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 336\u2013347. Springer, Heidelberg (2015)"},{"key":"47_CR8","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)"},{"issue":"3","key":"47_CR9","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 $$\\rm UP\\cap co$$ UP \u2229 co - $$\\rm UP$$ UP . Inform. Process. Lett. 68(3), 119\u2013124 (1998)","journal-title":"Inform. Process. Lett."},{"key":"47_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. 1770, pp. 290\u2013301. Springer, Heidelberg (2000)"},{"issue":"4","key":"47_CR11","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 J. Comput. 38(4), 1519\u20131532 (2008)","journal-title":"SIAM J. Comput."},{"key":"47_CR12","unstructured":"Kloks, T., Bodlaender, H.L.: On the treewidth and pathwidth of permutation graphs (1992). http:\/\/www.cs.uu.nl\/research\/techreps\/repo\/CS-1992\/1992-13.pdf"},{"issue":"2","key":"47_CR13","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 65(2), 149\u2013184 (1993)","journal-title":"Ann. Pure Appl. Logic"},{"key":"47_CR14","doi-asserted-by":"crossref","unstructured":"Mnich, M., R\u00f6glin, H., R\u00f6sner, C.: New deterministic algorithms for solving parity games.\u00a0arXiv.org, cs.CC, December 2015. http:\/\/arxiv.org\/abs\/1512.03246","DOI":"10.1007\/978-3-662-49529-2_47"},{"key":"47_CR15","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 $$ \u03bc -calculus model checking when tree-width is bounded. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 80\u201392. Springer, Heidelberg (2003)"},{"key":"47_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-540-74915-8_8","volume-title":"Computer Science Logic","author":"J Obdr\u017e\u00e1lek","year":"2007","unstructured":"Obdr\u017e\u00e1lek, J.: Clique-width and parity games. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 54\u201368. Springer, Heidelberg (2007)"},{"key":"47_CR17","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. 4855, pp. 449\u2013460. Springer, Heidelberg (2007)"},{"key":"47_CR18","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Concurrency Theory","author":"C Stirling","year":"1995","unstructured":"Stirling, C.: Local model checking games. In: Lee, I., Smolka, S.A. (eds.) CONCUR 1995. LNCS, vol. 962, pp. 1\u201311. Springer, Heidelberg (1995)"},{"key":"47_CR19","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)"},{"issue":"1\u20132","key":"47_CR20","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(1\u20132), 135\u2013183 (1998)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T21:29:24Z","timestamp":1748813364000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}