{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T13:23:51Z","timestamp":1749129831050},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642162411"},{"type":"electronic","value":"9783642162428"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16242-8_1","type":"book-chapter","created":{"date-parts":[[2010,10,4]],"date-time":"2010-10-04T08:51:59Z","timestamp":1286182319000},"page":"1-14","source":"Crossref","is-referenced-by-count":18,"title":["The Complexity of Partial-Observation Parity Games"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[]},{"given":"Laurent","family":"Doyen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1145\/585265.585270","volume":"49","author":"R. Alur","year":"2002","unstructured":"Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. Journal of the ACM\u00a049, 672\u2013713 (2002)","journal-title":"Journal of the ACM"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-540-78499-9_21","volume-title":"Foundations of Software Science and Computational Structures","author":"C. Baier","year":"2008","unstructured":"Baier, C., Bertrand, N., Gr\u00f6\u00dfer, M.: On decision problems for probabilistic B\u00fcchi automata. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol.\u00a04962, pp. 287\u2013301. Springer, Heidelberg (2008)"},{"key":"1_CR3","first-page":"319","volume-title":"LICS","author":"N. Bertrand","year":"2009","unstructured":"Bertrand, N., Genest, B., Gimbert, H.: Qualitative determinacy and decidability of stochastic games with signals. In: LICS, pp. 319\u2013328. IEEE Computer Society, Los Alamitos (2009)"},{"key":"1_CR4","unstructured":"Berwanger, D., Doyen, L.: On the power of imperfect information. In: FSTTCS, Dagstuhl Seminar Proceedings 08004. Internationales Begegnungs- und Forschungszentrum fuer Informatik, IBFI (2008)"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1090\/S0002-9947-1969-0280205-0","volume":"138","author":"J.R. B\u00fcchi","year":"1969","unstructured":"B\u00fcchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies. Transactions of the AMS\u00a0138, 295\u2013311 (1969)","journal-title":"Transactions of the AMS"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/978-3-642-15155-2_23","volume-title":"MFCS 2010","author":"K. Chatterjee","year":"2010","unstructured":"Chatterjee, K., Doyen, L., Gimbert, H., Henzinger, T.A.: Randomness for free. In: Hlineny, P. (ed.) MFCS 2010. LNCS, vol.\u00a06281, pp. 246\u2013257. Springer, Heidelberg (2010)"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A., Raskin, J.-F.: Algorithms for omega-regular games of incomplete information. Logical Methods in Computer Science\u00a03(3:4) (2007)","DOI":"10.2168\/LMCS-3(3:4)2007"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A.: Probabilistic automata on infinite words: Decidability and undecidability results. In: ATVA. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15643-4_1"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-45449-7_11","volume-title":"Embedded Software","author":"L. Alfaro de","year":"2001","unstructured":"de Alfaro, L., Henzinger, T.A.: Interface theories for component-based design. In: Henzinger, T.A., Kirsch, C.M. (eds.) EMSOFT 2001. LNCS, vol.\u00a02211, pp. 148\u2013165. Springer, Heidelberg (2001)"},{"key":"1_CR10","first-page":"368","volume-title":"FOCS","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.: Tree automata, mu-calculus and determinacy. In: FOCS, pp. 368\u2013377. IEEE, Los Alamitos (1991)"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Gimbert, H., Oualhadj, Y.: Probabilistic automata on finite words: Decidable and undecidable problems. In: Gavoille, C. (ed.) ICALP 2010, Part II. LNCS, vol.\u00a06199, pp. 527\u2013538. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-14162-1_44"},{"key":"1_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/978-3-642-02930-1_17","volume-title":"Automata, Languages and Programming","author":"V. Gripon","year":"2009","unstructured":"Gripon, V., Serre, O.: Qualitative concurrent stochastic games with imperfect information. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05556, pp. 200\u2013211. Springer, Heidelberg (2009)"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1006\/inco.2001.3085","volume":"173","author":"T.A. Henzinger","year":"2002","unstructured":"Henzinger, T.A., Kupferman, O., Rajamani, S.: Fair simulation. Information and Computation\u00a0173, 64\u201381 (2002)","journal-title":"Information and Computation"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","volume":"22","author":"N. Immerman","year":"1981","unstructured":"Immerman, N.: Number of quantifiers is better than number of tape cells. Journal of Computer and System Sciences\u00a022, 384\u2013406 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4190-4","volume-title":"Classical Descriptive Set Theory","author":"A. Kechris","year":"1995","unstructured":"Kechris, A.: Classical Descriptive Set Theory. Springer, Heidelberg (1995)"},{"issue":"2","key":"1_CR16","doi-asserted-by":"publisher","first-page":"363","DOI":"10.2307\/1971035","volume":"102","author":"D.A. Martin","year":"1975","unstructured":"Martin, D.A.: Borel determinacy. Annals of Mathematics\u00a0102(2), 363\u2013371 (1975)","journal-title":"Annals of Mathematics"},{"issue":"4","key":"1_CR17","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.2307\/2586667","volume":"63","author":"D.A. Martin","year":"1998","unstructured":"Martin, D.A.: The determinacy of Blackwell games. The Journal of Symbolic Logic\u00a063(4), 1565\u20131581 (1998)","journal-title":"The Journal of Symbolic Logic"},{"key":"1_CR18","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, 149\u2013184 (1993)","journal-title":"Annals of Pure and Applied Logic"},{"key":"1_CR19","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1993)"},{"key":"1_CR20","first-page":"179","volume-title":"POPL","author":"A. Pnueli","year":"1989","unstructured":"Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: POPL, pp. 179\u2013190. ACM Press, New York (1989)"},{"issue":"1","key":"1_CR21","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1137\/0325013","volume":"25","author":"P.J. Ramadge","year":"1987","unstructured":"Ramadge, P.J., Wonham, W.M.: Supervisory control of a class of discrete-event processes. SIAM Journal of Control and Optimization\u00a025(1), 206\u2013230 (1987)","journal-title":"SIAM Journal of Control and Optimization"},{"key":"1_CR22","first-page":"288","volume-title":"STOC","author":"J.H. Reif","year":"1979","unstructured":"Reif, J.H.: Universal games of incomplete information. In: STOC, pp. 288\u2013308. ACM Press, New York (1979)"},{"issue":"2","key":"1_CR23","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(84)90034-5","volume":"29","author":"J.H. Reif","year":"1984","unstructured":"Reif, J.H.: The complexity of two-player games of incomplete information. Journal of Computer and System Sciences\u00a029(2), 274\u2013301 (1984)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR24","first-page":"319","volume-title":"FOCS","author":"S. Safra","year":"1988","unstructured":"Safra, S.: On the complexity of \u03c9-automata. In: FOCS, pp. 319\u2013327. IEEE Computer Society Press, Los Alamitos (1988)"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Languages, automata, and logic. In: Handbook of Formal Languages, ch. 7, vol.\u00a03, Beyond Words, pp. 389\u2013455. Springer, Heidelberg (1997)","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"1_CR26","first-page":"327","volume-title":"FOCS","author":"M.Y. Vardi","year":"1985","unstructured":"Vardi, M.Y.: Automatic verification of probabilistic concurrent finite-state systems. In: FOCS, pp. 327\u2013338. IEEE Computer Society Press, Los Alamitos (1985)"}],"container-title":["Lecture Notes in Computer Science","Logic for Programming, Artificial Intelligence, and Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16242-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T02:02:39Z","timestamp":1559700159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16242-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642162411","9783642162428"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16242-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}