{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:19:13Z","timestamp":1781893153372,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540875307","type":"print"},{"value":"9783540875314","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87531-4_26","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T08:40:53Z","timestamp":1220085653000},"page":"354-368","source":"Crossref","is-referenced-by-count":11,"title":["The Descriptive Complexity of Parity Games"],"prefix":"10.1007","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erich","family":"Gr\u00e4del","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"1","key":"26_CR1","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/256292.256295","volume":"44","author":"S. Abiteboul","year":"1997","unstructured":"Abiteboul, S., Vardi, M.Y., Vianu, V.: Fixpoint logics, relational machines, and computational complexity. J. ACM\u00a044(1), 30\u201346 (1997)","journal-title":"J. ACM"},{"issue":"2","key":"26_CR2","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1006\/jcss.1995.1025","volume":"50","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Vianu, V.: Computing with first-order logic. Journal of Computer and System Sciences\u00a050(2), 309\u2013335 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1051\/ita:1999121","volume":"33","author":"A. Arnold","year":"1999","unstructured":"Arnold, A.: The mu-calculus alternation-depth is strict on binary trees. RAIRO Informatique Th\u00e9orique et Applications\u00a033, 329\u2013339 (1999)","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"26_CR4","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":"26_CR5","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/s00224-004-1147-5","volume":"37","author":"D. Berwanger","year":"2004","unstructured":"Berwanger, D., Gr\u00e4del, E.: Fixed-point logics and solitaire games. Theory of Computing Systems\u00a037, 675\u2013694 (2004)","journal-title":"Theory of Computing Systems"},{"key":"26_CR6","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-540-32275-7_15","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Berwanger","year":"2005","unstructured":"Berwanger, D., Gr\u00e4del, E.: Entanglement - A measure for the complexity of directed graphs with applications to logic and games. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 209\u2013223. Springer, Heidelberg (2005)"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0304-3975(97)00217-X","volume":"195","author":"J. Bradfield","year":"1998","unstructured":"Bradfield, J.: The modal \u03bc-calculus alternation hierarchy is strict. Theoretical Computer Science\u00a0195, 133\u2013153 (1998)","journal-title":"Theoretical Computer Science"},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(02)00578-9","volume":"299","author":"B. Courcelle","year":"2003","unstructured":"Courcelle, B.: The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications. Theoretical Computer Science\u00a0299, 1\u201336 (2003)","journal-title":"Theoretical Computer Science"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"65","DOI":"10.2178\/bsl\/1182353853","volume":"8","author":"A. Dawar","year":"2002","unstructured":"Dawar, A., Gurevich, Y.: Fixed point logics. Bulletin of Symbolic Logic\u00a08, 65\u201388 (2002)","journal-title":"Bulletin of Symbolic Logic"},{"key":"26_CR10","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Emerson, A., Jutla, C.: Tree automata, mu-calculus and determinacy. In: Proc. 32nd IEEE Symp. on Foundations of Computer Science, pp. 368\u2013377 (1991)","DOI":"10.1109\/SFCS.1991.185392"},{"key":"26_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68804-8_3","volume-title":"Finite Model Theory and Its Applications","author":"E. Gr\u00e4del","year":"2007","unstructured":"Gr\u00e4del, E., et al.: Finite Model Theory and Its Applications. Springer, Heidelberg (2007)"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1145\/507382.507388","volume":"3","author":"E. Gr\u00e4del","year":"2002","unstructured":"Gr\u00e4del, E., Hirsch, C., Otto, M.: Back and forth between guarded and modal logics. ACM Transactions on Computational Logic\u00a03, 418\u2013463 (2002)","journal-title":"ACM Transactions on Computational Logic"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Walukiewicz, I.: Positional determinacy of games with infinitely many priorities. Logical Methods in Computer Science (2006)","DOI":"10.2168\/LMCS-2(4:6)2006"},{"key":"26_CR15","unstructured":"Hunter, P.: Complexity and Infinite Games on Finite Graphs. PhD thesis, University of Cambridge (2007)"},{"key":"26_CR16","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 \u2229 Co-UP. Information Processing Letters\u00a068, 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"26_CR17","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":"26_CR18","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. In: Proceedings of ACM-SIAM Proceedings on Discrete Algorithms, SODA 2006, pp. 117\u2013123 (2006)","DOI":"10.1145\/1109557.1109571"},{"key":"26_CR19","unstructured":"Mostowski, A.: Games with forbidden positions. Technical Report Tech. Report 78, University of Gdansk (1991)"},{"key":"26_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/978-3-540-45069-6_7","volume-title":"Computer Aided Verification","author":"J. Obdrz\u00e1lek","year":"2003","unstructured":"Obdrz\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":"26_CR21","doi-asserted-by":"crossref","unstructured":"Obdrz\u00e1lek, J.: DAG-width - connectivity measure for directed graphs. In: Proceedings of ACM-SIAM Proceedings on Discrete Algorithms, SODA 2006, pp. 814\u2013821 (2006)","DOI":"10.1145\/1109557.1109647"},{"key":"26_CR22","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. Obdrz\u00e1lek","year":"2007","unstructured":"Obdrz\u00e1lek, J.: Clique-width and parity games. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol.\u00a04646, pp. 54\u201368. Springer, Heidelberg (2007)"},{"key":"26_CR23","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(98)00314-4","volume":"224","author":"M. Otto","year":"1999","unstructured":"Otto, M.: Bisimulation-invariant Ptime and higher-dimensional mu-calculus. Theoretical Computer Science\u00a0224, 237\u2013265 (1999)","journal-title":"Theoretical Computer Science"},{"key":"26_CR24","unstructured":"Stirling, C.: Bisimulation, model checking and other games. Notes for the Mathfit instructional meeting on games and computation. Edinburgh (1997)"},{"key":"26_CR25","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"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87531-4_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T19:04:40Z","timestamp":1738350280000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87531-4_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540875307","9783540875314"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87531-4_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}