{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:37:08Z","timestamp":1725514628964},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540693109"},{"type":"electronic","value":"9783540693116"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69311-6_16","type":"book-chapter","created":{"date-parts":[[2008,6,6]],"date-time":"2008-06-06T11:17:46Z","timestamp":1212751066000},"page":"135-146","source":"Crossref","is-referenced-by-count":0,"title":["A CSP-Based Approach for Solving Parity Game"],"prefix":"10.1007","author":[{"given":"Min","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Changle","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guoqing","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","unstructured":"Chen, X., Deng, X.: 3-NASH is PPAD-Complete. ECCC (2005) TR05-134"},{"key":"16_CR2","unstructured":"Chen, X., Deng, X.: Settling the Complexity of 2-player Nash Equilibrium. ECCC (2005) TR05-140"},{"key":"16_CR3","unstructured":"Daskalakis, C., Papadimitriou, C. H.: Three-Players Games are Hard. ECCC (2005) TR05-139"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J.F. Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative games. Annals of Mathematics\u00a0(54), 286\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Condon, A.: The complexity of stochastic games. Information and Computation, 203\u2013224 (1992)","DOI":"10.1016\/0890-5401(92)90048-K"},{"issue":"2","key":"16_CR6","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/1240233.1240247","volume":"3","author":"S.J. David","year":"2007","unstructured":"David, S.J.: The NP-completeness column: Finding needles in haystacks. ACM Transactions on Algorithms\u00a03(2), 24 (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/3-540-56922-7_32","volume-title":"Computer Aided Verification","author":"E.A. 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.\u00a0697, pp. 385\u2013396. Springer, Heidelberg (1993)"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/11537311_19","volume-title":"Fundamentals of Computation Theory","author":"B. Gartner","year":"2005","unstructured":"Gartner, B., Rust, L.: Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 209\u2013220. Springer, Heidelberg (2005)"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimtriou, C.H., Yannakakis, M.: How easy is local search? Journal of Computer and System Sciences\u00a037, 79\u2013100 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR10","unstructured":"Juba, B.: On the hardness of simple stochastic games (manuscript, 2004)"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzinski","year":"1998","unstructured":"Jurdzinski, M.: Deciding the winner in parity games is in UP and co-UP. Information Processing Letters\u00a068, 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N. Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: A note on total functions, existence theorems, and computational complexity. Theoretical Computer Science\u00a081, 317\u2013324 (1991)","journal-title":"Theoretical Computer Science"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences\u00a048, 498\u2013532 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1287\/mnsc.12.5.359","volume":"12","author":"A.J. Hoffman","year":"1966","unstructured":"Hoffman, A.J., Karp, R.M.: On Nonterminating Stochastic Games. Management Science\u00a012, 359\u2013370 (1966)","journal-title":"Management Science"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1007\/3-540-36494-3_58","volume-title":"STACS 2003","author":"H. Bjorklund","year":"2003","unstructured":"Bjorklund, H., Sandberg, S., Vorobyov, S.: A discrete subexponential algorithm for parity games. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 663\u2013674. Springer, Heidelberg (2003)"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Jurdzinski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. In: SODA 2006, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 117\u2013123 (2006)","DOI":"10.1145\/1109557.1109571"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Jurdzinski, M., Ics, B.R.: Small Progress Measures for Solving Parity Games. In: STACS 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17-19 (2000)","DOI":"10.1007\/3-540-46541-3_24"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Klarlund, N., Kozen, D.: Rabin measures and their applications to fairness and automatatheory. In: LICS 1991, Proceedings of Sixth Annual IEEE Symposium on Logic in Computer Science, pp. 256\u2013265 (1991)","DOI":"10.1109\/LICS.1991.151650"},{"key":"16_CR19","unstructured":"Puri, A.: Theory of hybrid systems and discrete event systems. Ph.D thesis, University of California, Berkeley (1996)"},{"key":"16_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. Voge","year":"2000","unstructured":"Voge, J., Jurdziiiski, 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":"16_CR21","volume-title":"Model Checking","author":"E.M. Clarke","year":"1999","unstructured":"Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (1999)"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Dhar, V., Ranganathan, N.: Integer Programming vs Expert Systems: An Experimental Comparison. Communications of the ACM, 323\u2013336 (1990)","DOI":"10.1145\/77481.77485"},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"de Kleer, J., Sussman, G.J.: Propagation of Constraints Applied to Circuit Synthesis. Circuit Theory and Applications, 127\u2013144 (1980)","DOI":"10.1002\/cta.4490080206"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"Davis, A.L., Rosenfeld, A.: Cooperating Processes for Low Level Vision: A Survey. Articial Intelligence, 245\u2013263 (1981)","DOI":"10.1016\/0004-3702(81)90026-6"},{"key":"16_CR25","volume-title":"Artificial Intelligence: a Modern Approach","author":"S. Russell","year":"2000","unstructured":"Russell, S., Norvig, P.: Artificial Intelligence: a Modern Approach. Prentice Hall, Englewood Cliffs (2000)"},{"key":"16_CR26","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy. In: FOCS 1991, Proceedings of 32nd Annual Symposium on Foundations of Computer Science, pp. 368\u2013377 (1991)","DOI":"10.1109\/SFCS.1991.185392"},{"key":"16_CR27","unstructured":"Mostowski, A.W.: Games with forbidden positions. Technical Report 78, University of Gdansk (1991)"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69311-6_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:34:49Z","timestamp":1620016489000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69311-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540693109","9783540693116"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69311-6_16","relation":{},"subject":[]}}