{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T04:41:03Z","timestamp":1745469663775,"version":"3.40.4"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,12,19]],"date-time":"2012-12-19T00:00:00Z","timestamp":1355875200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Synthese"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s11229-012-0215-7","type":"journal-article","created":{"date-parts":[[2012,12,18]],"date-time":"2012-12-18T11:03:15Z","timestamp":1355828595000},"page":"371-408","source":"Crossref","is-referenced-by-count":8,"title":["Exploring the tractability border in epistemic tasks"],"prefix":"10.1007","volume":"191","author":[{"given":"C\u00e9dric","family":"D\u00e9gremont","sequence":"first","affiliation":[]},{"given":"Lena","family":"Kurzen","sequence":"additional","affiliation":[]},{"given":"Jakub","family":"Szymanik","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,12,19]]},"reference":[{"issue":"1","key":"215_CR1","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.jal.2008.12.002","volume":"8","author":"T. \u00c5gotnes","year":"2010","unstructured":"\u00c5gotnes T., Balbiani P., Van Ditmarsch H., Seban P. (2010) Group announcement logic. Journal of Applied Logic 8(1): 62\u201381","journal-title":"Journal of Applied Logic"},{"issue":"1","key":"215_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11225-010-9227-9","volume":"94","author":"G. Aucher","year":"2010","unstructured":"Aucher G. (2010) An internal version of epistemic logic. Studia Logica 94(1): 1\u201322","journal-title":"Studia Logica"},{"issue":"3","key":"215_CR3","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s001820050111","volume":"28","author":"R. J. Aumann","year":"1999","unstructured":"Aumann R. J. (1999) Interactive epistemology I: Knowledge. International Journal of Game Theory 28(3): 263\u2013300","journal-title":"International Journal of Game Theory"},{"issue":"03","key":"215_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1017\/S1755020308080210","volume":"1","author":"P. Balbiani","year":"2008","unstructured":"Balbiani P., Baltag A., Van Ditmarsch H., Herzig A., Hoshi T., de Lima T. (2008) \u2018Knowable\u2019 as \u2018known after an announcement\u2019. The Review of Symbolic Logic 1(03): 305\u2013334","journal-title":"The Review of Symbolic Logic"},{"issue":"6A","key":"215_CR5","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/BF03180566","volume":"4","author":"J. L. Balc\u00e1zar","year":"1992","unstructured":"Balc\u00e1zar J. L., Gabarr\u00f3 J., Santha M. (1992) Deciding bisimilarity is P-complete. Formal Aspects of Computing 4(6A): 638\u2013648","journal-title":"Formal Aspects of Computing"},{"issue":"2","key":"215_CR6","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1023\/B:SYNT.0000024912.56773.5e","volume":"139","author":"A. Baltag","year":"2004","unstructured":"Baltag A., Moss L. S. (2004) Logics for epistemic programs. Synthese 139(2): 165\u2013224","journal-title":"Synthese"},{"key":"215_CR7","unstructured":"Baltag, A., Moss, L. S., & Solecki, S. (1998). The logic of public announcements, common knowledge, and private suspicions. In TARK \u201998: Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge, San Francisco, CA, USA, 1998 (pp. 43\u201356). Burlington, MA: Morgan Kaufmann Publishers Inc."},{"issue":"1\u20132","key":"215_CR8","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.artint.2005.01.005","volume":"164","author":"C. Baral","year":"2005","unstructured":"Baral C., Zhang Y. (2005) Knowledge updates: Semantics and complexity issues. Artificial Intelligence 164(1\u20132): 209\u2013243","journal-title":"Artificial Intelligence"},{"key":"215_CR9","unstructured":"Besold, T. R., Gust, H., Krumnack, U., Abdel-Fattah, A., Schmidt, M., & K\u00fchnberger, K.-U.. (2011). An argument for an analogical perspective on rationality and decision-making. In R. Verbrugge, & J. van Eijck (Eds.), Proceedings of the Workshop on Reasoning About Other Minds: Logical and Cognitive Perspectives (RAOM-2011), Groningen, The Netherland, 11 July 2011, volume 751 of CEUR Workshop Proceedings, (pp. 20\u201331). CEUR-WS.org."},{"key":"215_CR10","doi-asserted-by":"crossref","unstructured":"Blackburn, P., De Rijke, M., & Venema, Y. (2001). Modal logic. Number 53 in Cambridge Tracts in Theoretical Computer Science. Cambridge: Cambridge University Press.","DOI":"10.1017\/CBO9781107050884"},{"issue":"5","key":"215_CR11","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1109\/TKDE.2008.205","volume":"21","author":"L. De Nardo","year":"2009","unstructured":"De Nardo L., Ranzato F., Tapparo F. (2009) The subgraph similarity problem. IEEE Transactions on Knowledge and Data Engineering 21(5): 748\u2013749","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"215_CR12","unstructured":"De Rijke, M. (1993). Extending Modal Logic. PhD Thesis, ILLC, University of Amsterdam. ILLC Dissertation Series DS-93-04."},{"issue":"4","key":"215_CR13","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.1109\/TKDE.2003.1209024","volume":"15","author":"A. Dovier","year":"2003","unstructured":"Dovier A., Piazza C. (2003) The subgraph bisimulation problem. IEEE Transactions on Knowledge and Data Engineering 15(4): 1055\u20131056","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"215_CR14","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds J. (1965) Paths, trees, and flowers. Canadian Journal of Mathematics 17: 449\u2013467","journal-title":"Canadian Journal of Mathematics"},{"key":"215_CR15","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5803.001.0001","volume-title":"Reasoning about Knowledge","author":"R. Fagin","year":"1995","unstructured":"Fagin R., Halpern J. Y., Moses Y., Vardi M. Y. (1995) Reasoning about Knowledge. MIT Press, Cambridge, MA"},{"key":"215_CR16","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1111\/1468-0262.00125","volume":"68","author":"N. Feltovich","year":"2000","unstructured":"Feltovich N. (2000) Reinforcement-based vs. beliefs-based learning in experimental asymmetric- information games. Econometrica 68: 605\u2013641","journal-title":"Econometrica"},{"key":"215_CR17","unstructured":"French, T., & Van Ditmarsch, H. (2008). Undecidability for arbitrary public announcement logic. In C. Areces & R. Goldblatt (Eds.), Advances in Modal Logic (pp. 23\u201342). College Publications."},{"key":"215_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1990","unstructured":"Garey M. R., Johnson D. S. (1990) Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Co., New York"},{"key":"215_CR19","unstructured":"Gerbrandy, J. (1999). Bisimulations on Planet Kripke. PhD Thesis, ILLC, University of Amsterdam. ILLC Dissertation Series DS-1999-01."},{"key":"215_CR20","doi-asserted-by":"crossref","unstructured":"Gierasimczuk, N., & Szymanik, J. (2011a). Invariance properties of quantifiers and multiagent information exchange. In M. Kanazawa, A. Kornai, M. Kracht & H. Seki (Eds.), Proceedings of 12th Meeting on Mathematics of Language, volume 6878 of Lecture Notes in Computer Science (pp. 72\u201389). Berlin: Springer.","DOI":"10.1007\/978-3-642-23211-4_5"},{"key":"215_CR21","doi-asserted-by":"crossref","unstructured":"Gierasimczuk, N., & Szymanik, J. (2011b). A note on a generalization of the muddy children puzzle. In Krzysztof R. Apt, editor, Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2011), Groningen, The Netherlands, July 12\u201314, 2011, pages 257\u2013264. ACM","DOI":"10.1145\/2000378.2000409"},{"key":"215_CR22","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0004-3702(92)90049-4","volume":"54","author":"J. Y. Halpern","year":"1992","unstructured":"Halpern J. Y., Moses Y. (1992) A guide to completeness and complexity for modal logics of knowledge and belief. Artificial Intelligence 54: 319\u2013379","journal-title":"Artificial Intelligence"},{"issue":"1","key":"215_CR23","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-0000(89)90039-1","volume":"38","author":"J. Y. Halpern","year":"1989","unstructured":"Halpern J. Y., Vardi M. Y. (1989) The complexity of reasoning about knowledge and time. I. Lower bounds. Journal of Computer and Systems Science 38(1): 195\u2013237","journal-title":"Journal of Computer and Systems Science"},{"key":"215_CR24","unstructured":"Henzinger, M. R., Henzinger, T. A., & Kopke, P. W. (1995). Computing simulations on finite and infinite graphs. In FOCS \u201995: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (pp. 453\u2013462). IEEE Computer Society Press."},{"key":"215_CR25","doi-asserted-by":"crossref","unstructured":"Hoffmann, C. M. (1982). Group-theoretic algorithms and graph isomorphism, volume 136 of Lecture Notes in Computer Science. Berlin: Springer","DOI":"10.1007\/3-540-11493-9"},{"key":"215_CR26","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"Karp R. M. (1972) Reducibility among combinatorial problems. In: Miller R. E., Thatcher J. W. (eds) Complexity of Computer Computations. Plenum Press, New York, pp 85\u2013103"},{"key":"215_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity","author":"J. K\u00f6bler","year":"1993","unstructured":"K\u00f6bler J., Sch\u00f6ning U., Tor\u00e1n J. (1993) The Graph Isomorphism Problem: Its Structural Complexity. Birkhauser Verlag, Basel"},{"key":"215_CR28","first-page":"197","volume-title":"Advances in Modal Logic 2004","author":"B. Kooi","year":"2004","unstructured":"Kooi B., Van Benthem J. (2004) Reduction axioms for epistemic actions. In: Schmidt R., Pratt-Hartmann I., Reynolds M., Wansing H. (eds) Advances in Modal Logic 2004. Department of Computer Science, University of Manchester, Manchester, pp 197\u2013211"},{"key":"215_CR29","unstructured":"Ku\u010dera, A., & Mayr, R. (2002). Why is simulation harder than bisimulation?. In CONCUR \u201902: Proceedings of the 13th International Conference on Concurrency Theory (pp. 594\u2013610), London, UK, 2002. Berlin: Springer."},{"issue":"9","key":"215_CR30","doi-asserted-by":"crossref","first-page":"e45961,09","DOI":"10.1371\/journal.pone.0045961","volume":"7","author":"B. Meijering","year":"2012","unstructured":"Meijering B., Van Rijn H., Taatgen N. A., Verbrugge R. (2012) What eye movements can tell about theory of mind in a strategic game. PLoS ONE 7(9): e45961,09","journal-title":"PLoS ONE"},{"key":"215_CR31","volume-title":"A Course in Game Theory","author":"M. J. Osborne","year":"1994","unstructured":"Osborne M. J., Rubinstein A. (1994) A Course in Game Theory. MIT Press, Cambridge, MA"},{"key":"215_CR32","volume-title":"Computational Complexity","author":"C. H. Papadimitriou","year":"1993","unstructured":"Papadimitriou C. H. (1993) Computational Complexity. Addison Wesley, Boston"},{"key":"215_CR33","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C. H. Papadimitriou","year":"1982","unstructured":"Papadimitriou C. H., Steiglitz K. (1982) Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall Inc., Upper Saddle River, NJ"},{"key":"215_CR34","first-page":"201","volume-title":"Proceedings of the Fourth International Symposium on Methodologies for Intelligent Systems: Poster session program","author":"J. A. Plaza","year":"1989","unstructured":"Plaza J. A. (1989) Logics of public communications. In: Emrich M. L., Pfeifer M.S., Hadzikadic M., Ras Z. W. (eds) Proceedings of the Fourth International Symposium on Methodologies for Intelligent Systems: Poster session program. Oak Ridge National Laboratory, Oak Ridge, TN, pp 201\u2013216"},{"issue":"04","key":"215_CR35","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1017\/S1755020309990086","volume":"2","author":"I. Pratt-Hartmann","year":"2009","unstructured":"Pratt-Hartmann I., Moss L. S. (2009) Logics for the relational syllogistic. The Review of Symbolic Logic 2(04): 647\u2013683","journal-title":"The Review of Symbolic Logic"},{"key":"215_CR36","volume-title":"Modal Logic and Classical Logic","author":"J. Van Benthem","year":"1983","unstructured":"Van Benthem J. (1983) Modal Logic and Classical Logic. Bibliopolis, Naples"},{"key":"215_CR37","unstructured":"Van Benthem, J. (2010). Modal Logic for Open Minds. Number 199 in CSLI lecture notes. Stanford, CA: Center for the Study of Language and Information."},{"key":"215_CR38","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511974533","volume-title":"Logical Dynamics of Information Flow","author":"J. Van Benthem","year":"2011","unstructured":"Van Benthem J. (2011) Logical Dynamics of Information Flow. Cambridge University Press, Cambridge, MA"},{"key":"215_CR39","doi-asserted-by":"crossref","unstructured":"Van Benthem J., Pacuit E. (2006) The tree of knowledge in action: Towards a common perspective. In: Hodkinson I., Governatori G., Venema Y. (eds) Advances in Modal Logic. College Publications,","DOI":"10.1002\/9780470996751.ch27"},{"key":"215_CR40","unstructured":"Van Ditmarsch, H., & French, T. (2009). Simulation and information: Quantifying over epistemic events. In Knowledge Representation for Agents and Multi-Agent Systems: First International Workshop, KRAMAS 2008, Sydney, Australia, 17 September 2008, Revised Selected Papers (pp. 51\u201365), Berlin, Heidelberg, 2009. Berlin: Springer."},{"key":"215_CR41","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4020-5839-4","volume-title":"Dynamic Epistemic Logic","author":"H. Van Ditmarsch","year":"2007","unstructured":"Van Ditmarsch H., der Hoek W., Kooi B. (2007) Dynamic Epistemic Logic. Springer, Dordrecht"},{"issue":"6","key":"215_CR42","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1080\/03640210801897856","volume":"32","author":"I. Van Rooij","year":"2008","unstructured":"Van Rooij I. (2008) The tractable cognition thesis. Cognitive Science: A Multidisciplinary Journal 32(6): 939\u2013984","journal-title":"Cognitive Science: A Multidisciplinary Journal"},{"key":"215_CR43","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s10988-010-9076-z","volume":"33","author":"J. Szymanik","year":"2010","unstructured":"Szymanik J. (2010) Computational complexity of polyadic lifts of generalized quantifiers in natural language. Linguistics and Philosophy 33: 215\u2013250","journal-title":"Linguistics and Philosophy"},{"issue":"3","key":"215_CR44","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1111\/j.1551-6709.2009.01078.x","volume":"34","author":"J. Szymanik","year":"2010","unstructured":"Szymanik J., Zajenkowski M. (2010) Comprehension of simple quantifiers. Empirical evaluation of a computational model. Cognitive Science: A Multidisciplinary Journal 34(3): 521\u2013532","journal-title":"Cognitive Science: A Multidisciplinary Journal"},{"issue":"6","key":"215_CR45","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1007\/s10992-009-9115-9","volume":"38","author":"R. Verbrugge","year":"2009","unstructured":"Verbrugge R. (2009) Logic and social cognition. The facts matter, and so do computational models. Journal of Philosophical Logic 38(6): 649\u2013680","journal-title":"Journal of Philosophical Logic"},{"key":"215_CR46","unstructured":"Wang, Y. (2010). Epistemic Modelling and Protocol Dynamics. PhD Thesis, ILLC, University of Amsterdam. ILLC Dissertation Series DS-2010-06."},{"key":"215_CR47","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1023\/A:1013217320474","volume":"4","author":"R. Weber","year":"2001","unstructured":"Weber R. (2001) Behavior and learning in the \u201cdirty faces\u201d game. Experimental Economics 4: 229\u2013242","journal-title":"Experimental Economics"}],"container-title":["Synthese"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11229-012-0215-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11229-012-0215-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11229-012-0215-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T20:39:16Z","timestamp":1745440756000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11229-012-0215-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,19]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["215"],"URL":"https:\/\/doi.org\/10.1007\/s11229-012-0215-7","relation":{},"ISSN":["0039-7857","1573-0964"],"issn-type":[{"type":"print","value":"0039-7857"},{"type":"electronic","value":"1573-0964"}],"subject":[],"published":{"date-parts":[[2012,12,19]]}}}