Difference between revisions of "Public:Game Comonad Resources"

m (→‎Publications)
m (→‎Publications)
 
(32 intermediate revisions by the same user not shown)
Line 12: Line 12:
* Adam Ó Conghaile, Anuj Dawar. "Game Comonads & Generalised Quantifiers." [https://arxiv.org/abs/2006.16039 arXiv:2006.16039]
* Adam Ó Conghaile, Anuj Dawar. "Game Comonads & Generalised Quantifiers." [https://arxiv.org/abs/2006.16039 arXiv:2006.16039]
* Samson Abramsky and Nihil Shah. "Relating Structure and Power: Extended Version" [https://arxiv.org/abs/2010.06496 arXiv:2010.06496]
* Samson Abramsky and Nihil Shah. "Relating Structure and Power: Extended Version" [https://arxiv.org/abs/2010.06496 arXiv:2010.06496]
** Published version:
** Samson Abramsky, Nihil Shah, ''Relating structure and power: Comonadic semantics for computational resources''. Journal of Logic and Computation, Volume 31, Issue 6, September 2021, Pages 1390–1428, https://doi.org/10.1093/logcom/exab048
* Anuj Dawar. "Constraint Satisfaction, Graph Isomorphism, and the Pebbling Comonad." to appear
* Anuj Dawar. "Constraint Satisfaction, Graph Isomorphism, and the Pebbling Comonad." to appear
* Samson Abramsky, Luca Reggio. "Arboreal Categories: An Axiomatic Theory of Resources." [https://arxiv.org/abs/2102.08109 arXiv:2102.08109]
* Samson Abramsky, Luca Reggio. "Arboreal Categories: An Axiomatic Theory of Resources." [https://arxiv.org/abs/2102.08109 arXiv:2102.08109]
* Anuj Dawar, Tomáš Jakl, Luca Reggio. "Lovász-type Theorems and Game Comonads." [https://arxiv.org/abs/2105.03274 arXiv:2105.03274]
* Anuj Dawar, Tomáš Jakl, Luca Reggio. "Lovász-type Theorems and Game Comonads." [https://arxiv.org/abs/2105.03274 arXiv:2105.03274]
* Nihil Shah, "Restricting Power: The Pebble-Relation Comonad in Finite Model Theory." [https://www.cl.cam.ac.uk/events/act2021/papers/ACT_2021_paper_40.pdf ACT 2021 paper]
* Yoàv Montacute, Nihil Shah. The Pebble-Relation Comonad in Finite Model Theory [https://arxiv.org/abs/2110.08196 arXiv:2110.08196], '''won the Kleene student paper award at LiCS 2022!'''
* Samson Abramsky, Dan Marsden. Comonadic semantics for hybrid logic and bounded fragments [https://arxiv.org/abs/2110.09844 arXiv:2110.09844] (an improved version to appear at MFCS 2022)
* Luca Reggio. "Polyadic Sets and Homomorphism Counting" [https://arxiv.org/abs/2110.11061 arXiv:2110.11061]
* Samson Abramsky, Tomáš Jakl, Thomas Paine. Discrete Density Comonads and Graph Parameters. In: Hansen, H.H., Zanasi, F. (eds) Coalgebraic Methods in Computer Science. CMCS 2022. Lecture Notes in Computer Science, vol 13225. Springer, 2022. [https://arxiv.org/abs/2205.06589 arXiv:2205.06589] [https://doi.org/10.1007/978-3-031-10736-8_2 doi]
* Tomáš Jakl, Dan Marsden, Nihil Shah. Generalizations of Bilinear Maps -- Technical Report [https://arxiv.org/abs/2205.05382 arXiv:2205.05382]
* Tomáš Jakl, Dan Marsden, Nihil Shah. A game comonadic account of Courcelle and Feferman-Vaught-Mostowski theorems [https://arxiv.org/abs/2205.05387 arXiv:2205.05387]
* Samson Abramsky. "Structure and Power: an emerging landscape." Fundamenta Informaticae 186(1-4) : 1–26 (2022), https://doi.org/10.3233/FI-222116 [https://arxiv.org/abs/2206.07393 arXiv:2206.07393]
* Samson Abramsky. Notes on presheaf representations of strategies and cohomological refinements of k-consistency and k-equivalence [https://arxiv.org/abs/2206.12156 arXiv:2206.12156]
* Adam Ó Conghaile. Cohomology in Constraint Satisfaction and Structure Isomorphism [https://arxiv.org/abs/2206.15253 arXiv:2206.15253]
* Samson Abramsky, Luca Reggio. Arboreal Categories and Equi-resource Homomorphism Preservation Theorems [https://arxiv.org/abs/2211.15808 arXiv:2211.15808]
* Samson Abramsky, Yoàv Montacute, Nihil Shah. Linear Arboreal Categories [https://arxiv.org/abs/2301.10088 arXiv:2301.10088]
* Tomáš Jakl, Dan Marsden, Nihil Shah. A categorical account of composition methods in logic. [https://arxiv.org/abs/2010.06496 arXiv:2010.06496].
* Luca Reggio, Colin Riba: Finitely accessible arboreal adjunctions and Hintikka formulae [https://arxiv.org/abs/2304.12709 arXiv:2304.12709]
* Luca Reggio: A model category for modal logic, [https://arxiv.org/abs/2310.12068 arXiv:2310.12068]
* Nihil Shah and Amin Karamlou. ''No Go Theorems: Directed Containers That Do Not Distribute Over Distribution Monads'', Accepted at LiCS 2024.
* Yoàv Montacute and Glynn Winskel. ''Concurrent Games over Relational Structures ---the origin of game comonads'', Accepted at LiCS 2024.

Papers by people outside of the Resources and co-Resources grant:
* [https://bartoszjanbednarczyk.github.io/ Bartosz Bednarczyk], Mateusz Urbańczyk. [https://iccl.inf.tu-dresden.de/w/images/6/66/Comonadic.pdf Comonadic Semantics for Description Logics Games.] (2022).
* Mateusz Urbańczyk. Categorical Semantics for Model Comparison Games for Description Logics [https://arxiv.org/abs/2211.09655 arXiv:2211.09655]
* Gaurav Rattan, Tim Seppelt. Weisfeiler--Leman and Graph Spectra [https://arxiv.org/abs/2103.02972 arXiv:2103.02972] (which explains the relationship between linear-algebraic methods and the comonadic Lovasz-type arguments)
* Santiago Figueira, Gabriel Goren Roig: A Modal Logic with n-ary Relations Over Paths: Comonadic Semantics and Expressivity [https://arxiv.org/abs/2307.09679 arXiv:2307.09679]
* Moritz Lichter, Benedikt Pago, Tim Seppelt: Limitations of Game Comonads via Homomorphism Indistinguishability [https://arxiv.org/abs/2308.05693 arXiv:2308.05693]


Theses/reports:
Theses/reports:
* Nihil Shah: Game Comonads in Finite Model Theory (Master Thesis) [https://github.com/nihils/GameComonadsInFiniteModelTheory]
* Nihil Shah: Game Comonads in Finite Model Theory (Master thesis) [https://github.com/nihils/GameComonadsInFiniteModelTheory] (see README therein for corrections)
* Adam Ó Conghaile: Game comonads, descriptive complexity & finite model theory (First Year Report) [https://www.cl.cam.ac.uk/~ac891/images/FirstYearReport.pdf]
* Adam Ó Conghaile: Game comonads, descriptive complexity & finite model theory (First Year Report) [https://www.cl.cam.ac.uk/~ac891/images/FirstYearReport.pdf]
* Adam Ó Conghaile: Game comonads and beyond: compositional constructions for logic and algorithms [https://www.repository.cam.ac.uk/items/82e0220b-2419-4118-96ca-d62cba53ed8a], doi:10.17863/CAM.104155
* Thomas Paine: Structural Techniques in Descriptive Complexity (PhD thesis, submitted)


== Talks (with slides) ==
== Talks (slides and/or videos) ==


'''WARNING:''' This section is not updated much. It basically froze in late 2020. If you have given a talk on game comonads which is recorded or has public slides, please write it in here or let Tomas know about it.
⚫
Thomas Paine. Game Comonads and an application to the Equirank-variable conjecture (at MFPS 2020) [https://www.youtube.com/watch?v=L29VwwG6W88]

* Nihil Shah, "Restricting Power: The Pebble-Relation Comonad in Finite Model Theory" at ACT 2021 ([https://www.cl.cam.ac.uk/events/act2021/slides/ACT_2021_slides_40.pdf slides], [https://www.youtube.com/watch?v=We7FuoOCxyA&t=0s video]).
* Luca Reggio (j.w.w. Anuj Dawar, Tomáš Jakl) "Lovász-type Theorems and Game Comonads" at LICS 2021 [https://youtu.be/5TCjnEvAHOM].
* Daniel Marsden (j.w.w. Samson Abramsky) "Comonadic semantics for guarded fragments" at LICS 2021 [https://youtu.be/pqrGtghzjc4].
* Nihil Shah. "Bisimulation between hom sets and logics without counting" at Structure meets Power workshop 2021 ([https://www.cst.cam.ac.uk/files/smp-2021-slides-shah.pdf slides], [https://www.youtube.com/watch?v=nYX5-429Ucg video]).
* Luca Reggio. "Lovász-type theorems and polyadic spaces" at BLAST 2021 ([https://math.nmsu.edu/blast-2021/slides/Reggio.pdf slides]).
⚫
* Thomas Paine. "Game Comonads and an application to the Equirank-variable conjecture" at MFPS 2020 [https://www.youtube.com/watch?v=L29VwwG6W88].
* Adam Ó Conghaile. "k-Cores for game comonads" at [https://www.cs.ox.ac.uk/conferences/contextuality/ Contextuality 2019] ([https://www.cs.ox.ac.uk/conferences/contextuality/slidesAdamOConghaile.pdf slides]).


From [https://www.cst.cam.ac.uk/conference/coresources-2020/online-workshop Online Workshop on Resources and Co-Resources: A Junction between Semantics and Descriptive Complexity]:
From [https://www.cst.cam.ac.uk/conference/coresources-2020/online-workshop Online Workshop on Resources and Co-Resources: A Junction between Semantics and Descriptive Complexity]:
Line 36: Line 72:


Related:
Related:

* Nihil Shah - Cofree Comonads and their Uses (at LamdaConf), [https://www.youtube.com/watch?v=ydZ_fLwo9yI recording on youtube]
* Nihil Shah - Cofree Comonads and their Uses (at LamdaConf), [https://www.youtube.com/watch?v=ydZ_fLwo9yI recording on youtube]

== Other ==

* Dan Marsden recently started writing a blog called [https://stringdiagram.com/2022/05/30/strong-monads/ String Diagram] on monads, comonads and other related topics.

Latest revision as of 20:35, 25 April 2024

Publications

Papers

  • Samson Abramsky, Anuj Dawar, and Pengming Wang. "The pebbling comonad in finite model theory." 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 2017. arXiv:1704.05124
  • Anuj Dawar, Simone Severini, and Octavio Zapata. "Pebble games and cospectral graphs." Electronic Notes in Discrete Mathematics 61 (2017): 323-329. doi
  • Samson Abramsky and Nihil Shah. "Relating Structure and Power: Comonadic semantics for computational resources." International Workshop on Coalgebraic Methods in Computer Science. Springer, Cham, 2018. arXiv:1806.09031
  • Samson Abramsky. "Whither semantics?." Theoretical Computer Science 807 (2020): 3-14.
  • Samson Abramsky, Dan Marsden. "Comonadic semantics for guarded fragments." arXiv:2008.11094
  • Thomas Paine. "A Pebbling Comonad for Finite Rank and Variable Logic, and an Application to the Equirank-variable Homomorphism Preservation Theorem." Electronic Notes in Theoretical Computer Science, 352, 191-209. doi
  • Adam Ó Conghaile, Anuj Dawar. "Game Comonads & Generalised Quantifiers." arXiv:2006.16039
  • Samson Abramsky and Nihil Shah. "Relating Structure and Power: Extended Version" arXiv:2010.06496
    • Published version:
    • Samson Abramsky, Nihil Shah, Relating structure and power: Comonadic semantics for computational resources. Journal of Logic and Computation, Volume 31, Issue 6, September 2021, Pages 1390–1428, https://doi.org/10.1093/logcom/exab048
  • Anuj Dawar. "Constraint Satisfaction, Graph Isomorphism, and the Pebbling Comonad." to appear
  • Samson Abramsky, Luca Reggio. "Arboreal Categories: An Axiomatic Theory of Resources." arXiv:2102.08109
  • Anuj Dawar, Tomáš Jakl, Luca Reggio. "Lovász-type Theorems and Game Comonads." arXiv:2105.03274
  • Nihil Shah, "Restricting Power: The Pebble-Relation Comonad in Finite Model Theory." ACT 2021 paper
  • Yoàv Montacute, Nihil Shah. The Pebble-Relation Comonad in Finite Model Theory arXiv:2110.08196, won the Kleene student paper award at LiCS 2022!
  • Samson Abramsky, Dan Marsden. Comonadic semantics for hybrid logic and bounded fragments arXiv:2110.09844 (an improved version to appear at MFCS 2022)
  • Luca Reggio. "Polyadic Sets and Homomorphism Counting" arXiv:2110.11061
  • Samson Abramsky, Tomáš Jakl, Thomas Paine. Discrete Density Comonads and Graph Parameters. In: Hansen, H.H., Zanasi, F. (eds) Coalgebraic Methods in Computer Science. CMCS 2022. Lecture Notes in Computer Science, vol 13225. Springer, 2022. arXiv:2205.06589 doi
  • Tomáš Jakl, Dan Marsden, Nihil Shah. Generalizations of Bilinear Maps -- Technical Report arXiv:2205.05382
  • Tomáš Jakl, Dan Marsden, Nihil Shah. A game comonadic account of Courcelle and Feferman-Vaught-Mostowski theorems arXiv:2205.05387
  • Samson Abramsky. "Structure and Power: an emerging landscape." Fundamenta Informaticae 186(1-4) : 1–26 (2022), https://doi.org/10.3233/FI-222116 arXiv:2206.07393
  • Samson Abramsky. Notes on presheaf representations of strategies and cohomological refinements of k-consistency and k-equivalence arXiv:2206.12156
  • Adam Ó Conghaile. Cohomology in Constraint Satisfaction and Structure Isomorphism arXiv:2206.15253
  • Samson Abramsky, Luca Reggio. Arboreal Categories and Equi-resource Homomorphism Preservation Theorems arXiv:2211.15808
  • Samson Abramsky, Yoàv Montacute, Nihil Shah. Linear Arboreal Categories arXiv:2301.10088
  • Tomáš Jakl, Dan Marsden, Nihil Shah. A categorical account of composition methods in logic. arXiv:2010.06496.
  • Luca Reggio, Colin Riba: Finitely accessible arboreal adjunctions and Hintikka formulae arXiv:2304.12709
  • Luca Reggio: A model category for modal logic, arXiv:2310.12068
  • Nihil Shah and Amin Karamlou. No Go Theorems: Directed Containers That Do Not Distribute Over Distribution Monads, Accepted at LiCS 2024.
  • Yoàv Montacute and Glynn Winskel. Concurrent Games over Relational Structures ---the origin of game comonads, Accepted at LiCS 2024.

Papers by people outside of the Resources and co-Resources grant:

  • Bartosz Bednarczyk, Mateusz Urbańczyk. Comonadic Semantics for Description Logics Games. (2022).
  • Mateusz Urbańczyk. Categorical Semantics for Model Comparison Games for Description Logics arXiv:2211.09655
  • Gaurav Rattan, Tim Seppelt. Weisfeiler--Leman and Graph Spectra arXiv:2103.02972 (which explains the relationship between linear-algebraic methods and the comonadic Lovasz-type arguments)
  • Santiago Figueira, Gabriel Goren Roig: A Modal Logic with n-ary Relations Over Paths: Comonadic Semantics and Expressivity arXiv:2307.09679
  • Moritz Lichter, Benedikt Pago, Tim Seppelt: Limitations of Game Comonads via Homomorphism Indistinguishability arXiv:2308.05693

Theses/reports:

  • Nihil Shah: Game Comonads in Finite Model Theory (Master thesis) [1] (see README therein for corrections)
  • Adam Ó Conghaile: Game comonads, descriptive complexity & finite model theory (First Year Report) [2]
  • Adam Ó Conghaile: Game comonads and beyond: compositional constructions for logic and algorithms [3], doi:10.17863/CAM.104155
  • Thomas Paine: Structural Techniques in Descriptive Complexity (PhD thesis, submitted)

Talks (slides and/or videos)

WARNING: This section is not updated much. It basically froze in late 2020. If you have given a talk on game comonads which is recorded or has public slides, please write it in here or let Tomas know about it.

  • Nihil Shah, "Restricting Power: The Pebble-Relation Comonad in Finite Model Theory" at ACT 2021 (slides, video).
  • Luca Reggio (j.w.w. Anuj Dawar, Tomáš Jakl) "Lovász-type Theorems and Game Comonads" at LICS 2021 [4].
  • Daniel Marsden (j.w.w. Samson Abramsky) "Comonadic semantics for guarded fragments" at LICS 2021 [5].
  • Nihil Shah. "Bisimulation between hom sets and logics without counting" at Structure meets Power workshop 2021 (slides, video).
  • Luca Reggio. "Lovász-type theorems and polyadic spaces" at BLAST 2021 (slides).
  • Thomas Paine. "Game Comonads and an application to the Equirank-variable conjecture" at MFPS 2020 [6].
  • Adam Ó Conghaile. "k-Cores for game comonads" at Contextuality 2019 (slides).

From Online Workshop on Resources and Co-Resources: A Junction between Semantics and Descriptive Complexity:

  • Dan Marsden: Guards, Structure and Power
  • Adam Ó Conghaile: Game comonads and generalised quantifiers
  • Nihil Shah: Path-width and restricting conjunction in k-variable logic

Samson's talks on the topic:

  • Coalgebra Dreams [7]
  • Relating Structure to Power:Comonadic semantics for computational resources [8]

Related:

Other

  • Dan Marsden recently started writing a blog called String Diagram on monads, comonads and other related topics.
Retrieved from "https://kam.mff.cuni.cz/~jaklt/comonadwiki/index.php?title=Public:Game_Comonad_Resources&oldid=3322"