{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T06:29:20Z","timestamp":1775802560281,"version":"3.50.1"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T00:00:00Z","timestamp":1719792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>\n            Game comonads offer a categorical view of a number of model-comparison games central to model theory, such as pebble and Ehrenfeucht-Fra\u00efss\u00e9 games. Remarkably, the categories of coalgebras for these comon-ads capture preservation of several fragments of resource-bounded logics, such as (infinitary) first-order logic with\n            <jats:italic>n<\/jats:italic>\n            variables or bounded quantifier rank, and corresponding combinatorial parameters such as tree-width and tree-depth. In this way, game comonads provide a new bridge between categorical methods developed for semantics, and the combinatorial and algorithmic methods of resource-sensitive model theory.\n          <\/jats:p>","DOI":"10.1145\/3687256.3687260","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T16:33:01Z","timestamp":1722961981000},"page":"5-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["An Invitation to Game Comonads"],"prefix":"10.1145","volume":"11","author":[{"given":"Samson","family":"Abramsky","sequence":"first","affiliation":[{"name":"Department of Computer Science, University College London"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Reggio","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University College London"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.06.029"},{"key":"e_1_2_1_2_1","unstructured":"S. Abramsky. 2022a. Notes on presheaf representations of strategies and cohomological refinements of k-consistency and k-equivalence. Preprint available at https:\/\/arxiv.org\/abs\/2206.12156. (2022)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-222116"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005129"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-10736-8_2"},{"key":"e_1_2_1_6_1","unstructured":"S. Abramsky T. Laure and L. Reggio. 2024a. Existential and positive games: a comonadic and axiomatic view. (2024). Forthcoming."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470594"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2022.7"},{"key":"e_1_2_1_9_1","unstructured":"S. Abramsky Y. Montacute and N. Shah. 2024b. Linear arboreal categories. To appear in the proceedings of MFPS 2024 preprint available at https:\/\/arxiv.org\/abs\/2301.10088. (2024)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.115"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-19(3:14)2023"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2024.103423"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2018.2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exab048"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511600579"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31852"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004275029985"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/2272133"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107050884"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9884-z"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/1996573"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00017-1"},{"key":"e_1_2_1_23_1","volume-title":"Les pr\u00e9faisceaux comme mod\u00e8les des types d'homotopie. Ast\u00e9risque 308","author":"Cisinski D.-C.","year":"2006","unstructured":"D.-C. Cisinski. 2006. Les pr\u00e9faisceaux comme mod\u00e8les des types d'homotopie. Ast\u00e9risque 308 (2006), xxiv+390. http:\/\/numdam.org\/item\/AST_2006__308__R1_0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2022.75"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2021.16"},{"key":"e_1_2_1_26_1","unstructured":"M. Coste. 1976. Une approche logique des th\u00e9ories d\u00e9finissables par limites projectives finies. S\u00e9minaire B\u00e9nabou. Universit\u00e9 Paris-Nord. https:\/\/perso.univ-rennes1.fr\/michel.coste\/publis\/limfinies.pdf"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470609"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20461"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"e_1_2_1_30_1","volume-title":"Complexity of computation (Proc. SIAM-AMS Sympos.).","author":"Fagin R.","unstructured":"R. Fagin. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of computation (Proc. SIAM-AMS Sympos.). Vol. VII. Amer. Math. Soc., Providence, RI, 43--73."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_32_1","first-page":"35","article-title":"Sur quelques classifications des syst\u00e8mes de relations","volume":"1","author":"Fra\u00efss\u00e9 R.","year":"1954","unstructured":"R. Fra\u00efss\u00e9. 1954. Sur quelques classifications des syst\u00e8mes de relations. Publ. Sci. Univ. Alger. S\u00e9r. A 1 (1954), 35--182.","journal-title":"Publ. Sci. Univ. Alger. S\u00e9r. A"},{"key":"e_1_2_1_33_1","volume-title":"Lecture Notes in Mathematics","volume":"221","author":"Gabriel P.","unstructured":"P. Gabriel and F. Ulmer. 1971. Lokal pr\u00e4sentierbare Kategorien. Lecture Notes in Mathematics, Vol. 221. Springer-Verlag, Berlin-New York."},{"key":"e_1_2_1_34_1","volume-title":"Why are modal logics so robustly decidable? World Scientific Publishing Co","author":"Gr\u00e4del E.","unstructured":"E. Gr\u00e4del. 2001. Why are modal logics so robustly decidable? World Scientific Publishing Co., Inc., 393--408."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"E. Gr\u00e4del P. G. Kolaitis L. Libkin M. Marx J. Spencer M. Y. Vardi Y. Venema and S. Weinstein. 2007. Finite Model Theory and Its Applications (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag Berlin Heidelberg. xiii+440 pages. 10.1007\/3-540-68804-8","DOI":"10.1007\/3-540-68804-8"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394739"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0070"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"M. Hennessy and R. Milner. 1980. On Observing Nondeterminism and Concurrency. In 7th Colloquium on Automata Languages and Programming (ICALP). 299--309. 10.1007\/3-540-10003-2_79","DOI":"10.1007\/3-540-10003-2_79"},{"key":"e_1_2_1_39_1","volume-title":"Model categories and their localizations. Mathematical Surveys and Monographs","author":"Hirschhorn P. S.","unstructured":"P. S. Hirschhorn. 2003. Model categories and their localizations. Mathematical Surveys and Monographs, Vol. 99. American Mathematical Society, Providence, RI. xvi+457 pages."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/6.1.57"},{"key":"e_1_2_1_41_1","volume-title":"A Normal Form for Algebraic Constructions II. Logique et Analyse 18, 71\/72","author":"Hodges W.","year":"1975","unstructured":"W. Hodges. 1975. A Normal Form for Algebraic Constructions II. Logique et Analyse 18, 71\/72 (1975), 429--487. http:\/\/www.jstor.org\/stable\/44083994"},{"key":"e_1_2_1_42_1","volume-title":"Quad. Mat.","volume":"11","author":"Hrushovski E.","year":"2002","unstructured":"E. Hrushovski. 2002. Pseudo-finite fields and related structures. In Model theory and applications. Quad. Mat., Vol. 11. Aracne, Rome, 151--212."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(91)90099-N"},{"key":"e_1_2_1_46_1","unstructured":"T. Jakl D. Marsden and N. Shah. 2022. A game comonadic account of Courcelle and Feferman-Vaught-Mostowski theorems. Preprint available at https:\/\/arxiv.org\/abs\/2205.05387. (2022)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS56636.2023.10175751"},{"key":"e_1_2_1_48_1","volume-title":"Sketches of an elephant: a topos theory compendium","author":"Johnstone P. T.","unstructured":"P. T. Johnstone. 2002. Sketches of an elephant: a topos theory compendium. Vol. 2. Oxford Logic Guides, Vol. 44. The Clarendon Press, Oxford University Press, Oxford."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(81)90052-9"},{"key":"e_1_2_1_50_1","unstructured":"A. Joyal. 2008. The Theory of Quasi-Categories and its Applications. (2008). https:\/\/mat.uab.cat\/~kock\/crm\/hocat\/advanced-course\/Quadern45-2.pdf Lectures for the Advanced Course on Simplicial Methods in Higher Categories CRM."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)90069-8"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1993.287566"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0057"},{"key":"e_1_2_1_54_1","volume-title":"Theory of Models (Proc. 1963 Internat. Sympos.","author":"Karp C. R.","unstructured":"C. R. Karp. 1965. Finite-quantifier equivalence. In Theory of Models (Proc. 1963 Internat. Sympos. Berkeley). North-Holland, Amsterdam, 407--412."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90021-7"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1055"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/7.4.501"},{"key":"e_1_2_1_58_1","unstructured":"J. van Leeuwen (Ed.). 1990a. Handbook of theoretical computer science. Vol. A. Elsevier Science Publishers B.V. Amsterdam; MIT Press Cambridge MA. x+996 pages. Algorithms and complexity."},{"key":"e_1_2_1_59_1","unstructured":"J. van Leeuwen (Ed.). 1990b. Handbook of theoretical computer science. Vol. B. Elsevier Science Publishers B.V. Amsterdam; MIT Press Cambridge MA. xiv+1273 pages. Formal models and semantics."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-42-1-38-54"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1959.9.143"},{"key":"e_1_2_1_64_1","first-page":"1","article-title":"Monads of effective descent type and comonadicity","volume":"16","author":"Mesablishvili B.","year":"2006","unstructured":"B. Mesablishvili. 2006. Monads of effective descent type and comonadicity. Theory Appl. Categ. 16, 1 (2006), 1--45. http:\/\/www.tac.mta.ca\/tac\/volumes\/16\/1\/16-01abs.html","journal-title":"Theory Appl. Categ."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533335"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974960"},{"key":"e_1_2_1_68_1","unstructured":"M. Otto. 2023. Graded modal logic and counting bisimulation. Preprint available at https:\/\/arxiv.org\/abs\/1910.00039. (2023)."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2020.09.010"},{"key":"e_1_2_1_70_1","first-page":"155","article-title":"Isomorphism types of objects in categories determined by numbers of morphisms","volume":"35","author":"Pultr A.","year":"1973","unstructured":"A. Pultr. 1973. Isomorphism types of objects in categories determined by numbers of morphisms. Acta Scientiarum Mathematicarum 35 (1973), 155--160.","journal-title":"Acta Scientiarum Mathematicarum"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0097438"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2022.108712"},{"key":"e_1_2_1_73_1","unstructured":"L. Reggio. 2023. A model category for modal logic. Preprint available at https:\/\/arxiv.org\/abs\/2310.12068. (2023)."},{"key":"e_1_2_1_74_1","unstructured":"L. Reggio and C. Riba. 2023. Finitely accessible arboreal adjunctions and Hintikka formulae. (2023). Preprint available at https:\/\/arxiv.org\/abs\/2304.12709."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107261457"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008275906015"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379763"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.2307\/2964569"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1385-7258(55)50009-6"},{"key":"e_1_2_1_81_1","volume-title":"The impossibility of an algorithm for the decision problem for finite domains. Doklady Akad. Nauk SSSR (N.S.)","author":"Trakhtenbrot B. A.","year":"1950","unstructured":"B. A. Trakhtenbrot. 1950. The impossibility of an algorithm for the decision problem for finite domains. Doklady Akad. Nauk SSSR (N.S.) (1950), 569--572."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(68)90036-7"},{"key":"e_1_2_1_83_1","volume-title":"Pseudo-finite model theory","author":"V\u00e4\u00e4n\u00e4nen J.","year":"2001","unstructured":"J. V\u00e4\u00e4n\u00e4nen. 2003. Pseudo-finite model theory. Vol. 24. 169--183. http:\/\/www.mat.unb.br\/~matcont\/volume24.html 8th Workshop on Logic, Language, Informations and Computation---WoLLIC 2001 (Bras\u00edlia)."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnp080"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3687256.3687260","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3687256.3687260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:02Z","timestamp":1750294682000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3687256.3687260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":84,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.1145\/3687256.3687260"],"URL":"https:\/\/doi.org\/10.1145\/3687256.3687260","relation":{},"ISSN":["2372-3491"],"issn-type":[{"value":"2372-3491","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}