Resources and Co-Resources: a junction between categorical semantics, model theory and descriptive complexity

Add to your list(s) Download to your calendar using vCal

• Samson Abramsky, University of Oxford
• Friday 06 December 2019, 11:00-12:00
• Computer Science, The Sloman Lounge (UG).

If you have a question about this talk, please contact Jamie Vicary.

There is a remarkable divide in the field of logic in Computer Science, between two distinct strands: one focussing on semantics and compositionality (“Structure”), the other on expressiveness and complexity (“Power”). It is remarkable because these two fundamental aspects are studied using almost disjoint technical languages and methods, by almost disjoint research communities. We believe that bridging this divide is a major issue in Computer Science, and may hold the key to fundamental advances in the field.

In this talk, we describe a novel approach to relating categorical semantics, which exemplifies the first strand, to finite model theory, which exemplifies the second. It is based on [1, 2], and is the focus of a joint research project with Anuj Dawar.

[1] Samson Abramsky, Anuj Dawar, and Pengming Wang. The pebbling comonad in finite model theory. In Logic in Computer Science (LICS), 2017 32nd Annual ACM /IEEE Symposium on, pages 1–12. IEEE , 2017.

[2] Samson Abramsky and Nihil Shah. Relating Structure and Power: Comonadic semantics for computational resources. In 27th EACSL Annual Conference on Computer Science Logic, CSL 2018 , September 4-7, 2018, Birmingham, UK, pages 2:1–2:17, 2018.

This talk is part of the Theoretical computer science seminar series.

This talk is included in these lists:

• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Computer Science, The Sloman Lounge (UG)
• computer sience

Note that ex-directory lists are not shown.