{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T06:29:19Z","timestamp":1775802559041,"version":"3.50.1"},"reference-count":49,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2021,8,10]],"date-time":"2021-08-10T00:00:00Z","timestamp":1628553600000},"content-version":"vor","delay-in-days":1,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,9,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Combinatorial games are widely used in finite model theory, constraint satisfaction, modal logic and concurrency theory to characterize logical equivalences between structures. In particular, Ehrenfeucht\u2013Fra\u00efss\u00e9 games, pebble games and bisimulation games play a central role. We show how each of these types of games can be described in terms of an indexed family of comonads on the category of relational structures and homomorphisms. The index $k$ is a resource parameter that bounds the degree of access to the underlying structure. The coKleisli categories for these comonads can be used to give syntax-free characterizations of a wide range of important logical equivalences. Moreover, the coalgebras for these indexed comonads can be used to characterize key combinatorial parameters: tree depth for the Ehrenfeucht\u2013Fra\u00efss\u00e9 comonad, tree width for the pebbling comonad and synchronization tree depth for the modal unfolding comonad. These results pave the way for systematic connections between two major branches of the field of logic in computer science, which hitherto have been almost disjoint: categorical semantics and finite and algorithmic model theory.<\/jats:p>","DOI":"10.1093\/logcom\/exab048","type":"journal-article","created":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T19:19:42Z","timestamp":1627931982000},"page":"1390-1428","source":"Crossref","is-referenced-by-count":10,"title":["Relating structure and power: Comonadic semantics for computational resources"],"prefix":"10.1093","volume":"31","author":[{"given":"Samson","family":"Abramsky","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nihil","family":"Shah","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,8,9]]},"reference":[{"key":"2022021005492727900_ref1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2019.06.029","article-title":"Whither semantics","volume":"807","author":"Abramsky","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"2022021005492727900_ref2","first-page":"35:1","article-title":"The quantum monad on relational structures","volume-title":"Proceedings of 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017","author":"Abramsky","year":"2018"},{"key":"2022021005492727900_ref3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/LICS.2017.8005129","article-title":"The pebbling comonad in finite model theory","volume-title":"Logic in Computer Science (LICS), 2017 32nd Annual ACM\/IEEE Symposium on","author":"Abramsky","year":"2017"},{"key":"2022021005492727900_ref4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/LICS52264.2021.9470594","article-title":"Comonadic semantics for guarded fragments","volume-title":"2021 36th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)","author":"Abramsky","year":"2021"},{"key":"2022021005492727900_ref5","first-page":"2:1","article-title":"Relating structure and power: comonadic semantics for computational resources","volume-title":"27th EACSL Annual Conference on Computer Science Logic, CSL 2018","author":"Abramsky","year":"2018"},{"key":"2022021005492727900_ref6","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2010.10.019","article-title":"Resource bisimilarity and graded bisimilarity coincide","volume":"111","author":"Aceto","year":"2010","journal-title":"Information Processing Letters"},{"key":"2022021005492727900_ref7","first-page":"74","article-title":"When is a container a comonad","volume-title":"International Conference on Foundations of Software Science and Computational Structures","author":"Ahman","year":"2012"},{"key":"2022021005492727900_ref8","first-page":"297","article-title":"Monads need not be endofunctors","volume-title":"International Conference on Foundations of Software Science and Computational Structures","author":"Altenkirch","year":"2010"},{"key":"2022021005492727900_ref9","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1023\/A:1004275029985","article-title":"Johan van Benthem. Modal languages and bounded fragments of predicate logic","volume":"27","author":"Andr\u00e9ka","year":"1998","journal-title":"Journal of Philosophical Logic"},{"key":"2022021005492727900_ref10","article-title":"Modal logic","volume-title":"Cambridge Tracts in Theoretical Computer Science","author":"Blackburn","year":"2002"},{"key":"2022021005492727900_ref11","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1305\/ndjfl\/1039886524","article-title":"On elementary equivalence for equality-free logic","volume":"37","author":"Casanovas","year":"1996","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"2022021005492727900_ref12","first-page":"77","article-title":"Optimal implementation of conjunctive queries in relational data bases","volume-title":"Proceedings of the Ninth Annual ACM Symposium on Theory of Computing","author":"Chandra","year":"1977"},{"key":"2022021005492727900_ref13","first-page":"16:1","article-title":"Game comonads and generalised quantifiers","volume-title":"29th EACSL Annual Conference on Computer Science Logic (CSL 2021)","author":"Conghaile","year":"2021"},{"key":"2022021005492727900_ref14","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/3-540-46691-6_31","article-title":"Graded modalities and resource bisimulation","volume-title":"International Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Corradini","year":"1999"},{"key":"2022021005492727900_ref15","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Information and Computation"},{"key":"2022021005492727900_ref16","first-page":"310","article-title":"Constraint satisfaction, bounded treewidth, and finite-variable logics","volume-title":"International Conference on Principles and Practice of Constraint Programming","author":"Dalmau","year":"2002"},{"key":"2022021005492727900_ref17","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1023\/A:1005245900406","article-title":"A note on graded modal logic","volume":"64","author":"de Rijke","year":"2000","journal-title":"Studia Logica"},{"key":"2022021005492727900_ref18","volume-title":"Finite Model Theory","author":"Ebbinghaus","year":"2005"},{"key":"2022021005492727900_ref19","doi-asserted-by":"crossref","first-page":"13","DOI":"10.4064\/fm-49-2-129-141","article-title":"An application of games to the completeness problem for formalized theories","volume":"49","author":"Ehrenfeucht","year":"1961","journal-title":"Fundamenta Mathematicae"},{"key":"2022021005492727900_ref20","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1215\/ijm\/1256068141","article-title":"Adjoint functors and triples","volume":"9","author":"Eilenberg","year":"1965","journal-title":"Illinois Journal of Mathematics"},{"key":"2022021005492727900_ref21","first-page":"35","article-title":"Sur quelques classifications des syst\u00e8mes de relations","volume-title":"Publications Scientifiques, S\u00e9rie A","author":"Fra\u00efss\u00e9","year":"1954"},{"key":"2022021005492727900_ref22","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1145\/3022670.2951939","article-title":"Combining effects and coeffects via grading","volume":"51","author":"Gaboardi","year":"2016","journal-title":"ACM SIGPLAN Notices"},{"key":"2022021005492727900_ref23","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/3-540-48660-7_3","article-title":"Decision procedures for guarded logics","volume-title":"16th International Conference on Automated Deduction","author":"Gr\u00e4del","year":"1999"},{"key":"2022021005492727900_ref24","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-319-06025-5_1","article-title":"The freedoms of (guarded) bisimulation","volume-title":"Johan van Benthem on Logic and Information Dynamics","author":"Gr\u00e4del","year":"2014"},{"key":"2022021005492727900_ref25","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"Hell","year":"2004"},{"key":"2022021005492727900_ref26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1996.0070","article-title":"Logical hierarchies in PTIME","volume":"121","author":"Hella","year":"1996","journal-title":"Information and Computation"},{"key":"2022021005492727900_ref27","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/3-540-10003-2_79","article-title":"On observing nondeterminism and concurrency","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Hennessy","year":"1980"},{"key":"2022021005492727900_ref28","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1109\/LICS.1993.287566","article-title":"Bisimulation and open maps","volume-title":"[1993] Proceedings Eighth Annual IEEE Symposium on Logic in Computer Science","author":"Joyal","year":"1993"},{"key":"2022021005492727900_ref29","article-title":"Treewidth: computations and approximations","volume-title":"Springer Lecture Notes in Computer Science","author":"Kloks","year":"1994"},{"key":"2022021005492727900_ref30","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/298514.298542","article-title":"On the expressive power of Datalog: tools and a case study","volume-title":"Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"Kolaitis","year":"1990"},{"key":"2022021005492727900_ref31","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","article-title":"Infinitary logics and 0\u20131 laws","volume":"98","author":"Kolaitis","year":"1992","journal-title":"Information and Computation"},{"key":"2022021005492727900_ref32","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory (Texts in Theoretical Computer Science. An EATCS Series)","author":"Libkin","year":"2004"},{"key":"2022021005492727900_ref33","article-title":"Categories for the working mathematician","volume-title":"Graduate Texts in Mathematics","author":"Lane","year":"2013"},{"key":"2022021005492727900_ref34","article-title":"Algebraic theories","volume-title":"Graduate Texts in Mathematics","author":"Manes","year":"2012"},{"key":"2022021005492727900_ref35","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-10235-3","article-title":"A calculus of communicating systems","volume-title":"Springer Lecture Notes in Comput. Science","author":"Milner","year":"1980"},{"key":"2022021005492727900_ref36","article-title":"Communication and concurrency","volume-title":"Prentice Hall International Series in Computer Science","author":"Milner","year":"1989"},{"key":"2022021005492727900_ref37","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0890-5401(91)90052-4","article-title":"Notions of computation and monads","volume":"93","author":"Moggi","year":"1991","journal-title":"Information and Computation"},{"key":"2022021005492727900_ref38","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","article-title":"Tree-depth, subgraph coloring and homomorphism bounds","volume":"27","author":"Ne\u0161et\u0159il","year":"2006","journal-title":"European Journal of Combinatorics"},{"key":"2022021005492727900_ref39","article-title":"Programming contextual computations","volume-title":"Technical Report UCAM-CL-TR-854","author":"Orchard","year":"2014"},{"key":"2022021005492727900_ref40","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.entcs.2020.09.010","article-title":"A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem","volume":"352","author":"Paine","year":"2020","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"2022021005492727900_ref41","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1379759.1379763","article-title":"Homomorphism preservation theorems","volume":"55","author":"Rossman","year":"2008","journal-title":"JACM"},{"key":"2022021005492727900_ref42","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1516507.1516510","article-title":"On the origins of bisimulation and coinduction","volume":"31","author":"Sangiorgi","year":"2009","journal-title":"ACM Transactions on Programming Languages and Systems (TOPLAS)"},{"key":"2022021005492727900_ref43","first-page":"329","article-title":"Logic with denumerably long formulas and finite strings of quantifiers","volume-title":"The Theory of Models","author":"Scott","year":"1963"},{"key":"2022021005492727900_ref44","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/BF02771574","article-title":"Every two elementarily equivalent models have isomorphic ultrapowers","volume":"10","author":"Shelah","year":"1971","journal-title":"Israel Journal of Mathematics"},{"key":"2022021005492727900_ref45","volume-title":"Database and Knowledge-Based Systems, Vols. I and II","author":"Ullman","year":"1989"},{"key":"2022021005492727900_ref46","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0021-8693(68)90036-7","article-title":"Properties of dense and relative adjoint functors","volume":"8","author":"Ulmer","year":"1968","journal-title":"Journal of Algebra"},{"key":"2022021005492727900_ref47","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/j.entcs.2008.05.029","article-title":"Comonadic notions of computation","volume":"203","author":"Uustalu","year":"2008","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"2022021005492727900_ref48","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511611193","article-title":"Dependence logic: a new approach to independence friendly logic","volume-title":"London Mathematical Society student texts","author":"V\u00e4\u00e4n\u00e4nen","year":"2007"},{"key":"2022021005492727900_ref49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/oso\/9780198537809.003.0001","article-title":"Models for concurrency","volume-title":"Handbook of Logic in Computer Science","author":"Winskel","year":"1995"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/31\/6\/1390\/42432010\/exab048.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/31\/6\/1390\/42432010\/exab048.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:26:35Z","timestamp":1725557195000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/31\/6\/1390\/6343072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,9]]},"references-count":49,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,8,9]]},"published-print":{"date-parts":[[2021,9,3]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exab048","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,9]]},"published":{"date-parts":[[2021,8,9]]}}}