Guards, Structure and Power -- Dan Marsden

Duration: 1 hour 10 mins

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/3194295/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	(No description)


Created:	2020-04-01 18:09
Collection:	Online Workshop: Resources and Co-Resources: A Junction between Semantics and Descriptive Complexity
Publisher:	University of Cambridge
Copyright:	Daniel Marsden
Language:	eng (English)


Abstract:	In this talk we shall describe recent work at Oxford, developing a structural understanding of bisimulation games for various guarded fragments of first order logic. Intuitively, these guarded logics are wide generalisations of conventional modal logics, gaining superior expressive power, whilst retaining attractive computational characteristics. Our eventual aim is to identify the structural reasons why these logics have such desirable computational and model theoretic properties. Our analysis builds upon the earlier work of Abramsky, Dawar, Wang and Shah exhibiting an exciting connection between two apparently disparate fields: * The study of the power of computational methods, as typified by finite model theory and descriptive complexity * The investigation of the structure of computational phenomena, characteristic of program semantics and particularly categorical methods The divide is bridged by a novel comonadic perspective on model comparison games such as the pebbling and Ehrenfeuct-Fraisse games. The framework also has quantitative aspects, via natural gradings that capture resource theoretic aspects on the phenomena involved. It is these techniques that we aim extend to the guarded setting in our new work. The talk will aim to be reasonably self contained. We shall provide an introduction to the comonadic approach to model comparison games, and background on the various logical fragments of interest. This is work in progress, jointly with Samson Abramsky, Tom Paine, and Nihil Shah at Oxford slides: https://www.cst.cam.ac.uk/sites/www.cst.cam.ac.uk/files/guards.pdf

Abstract:

In this talk we shall describe recent work at Oxford, developing a structural understanding of bisimulation games for various guarded fragments of first order logic. Intuitively, these guarded logics are wide generalisations of conventional modal logics, gaining superior expressive power, whilst retaining attractive computational characteristics. Our eventual aim is to identify the structural reasons why these logics have such desirable computational and model theoretic properties.

Our analysis builds upon the earlier work of Abramsky, Dawar, Wang and Shah exhibiting an exciting connection between two apparently disparate fields:

* The study of the power of computational methods, as typified by finite model theory and descriptive complexity
* The investigation of the structure of computational phenomena, characteristic of program semantics and particularly categorical methods

The divide is bridged by a novel comonadic perspective on model comparison games such as the pebbling and Ehrenfeuct-Fraisse games. The framework also has quantitative aspects, via natural gradings that capture resource theoretic aspects on the phenomena involved. It is these techniques that we aim extend to the guarded setting in our new work.

The talk will aim to be reasonably self contained. We shall provide an introduction to the comonadic approach to model comparison games, and background on the various logical fragments of interest.

This is work in progress, jointly with Samson Abramsky, Tom Paine, and Nihil Shah at Oxford

slides: https://www.cst.cam.ac.uk/sites/www.cst.cam.ac.uk/files/guards.pdf

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	1152x720	2.15 Mbits/sec	1.11 GB	View	Download
MPEG-4 Video	576x360	662.2 kbits/sec	339.51 MB	View	Download
WebM	576x360	309.98 kbits/sec	158.93 MB	View	Download
iPod Video	480x360	523.91 kbits/sec	268.61 MB	View	Download
MP3	44100 Hz	251.71 kbits/sec	129.05 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)