Path-width and restricting conjunction in k-variable logic -- Nihil Shah
Duration: 33 mins 46 secs
Share this media item:
Embed this media item:
Embed this media item:
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: | Nihil Shah |
| Language: | eng (English) |
| Abstract: | This talk will be about ongoing work on a subcomonad of the pebbling comonad. This subcomona captures a restriction of k-variable logic that imposes a restriction on conjunctions in a formula. In analogy with the characterization of tree-width as the coalgebra number, I will show that this subcomonad characterizes path-width. As a bonus, I will discuss ongoing work on clique-width and other graph parameters.
slides: https://www.cst.cam.ac.uk/sites/www.cst.cam.ac.uk/files/pebble_relation_comonad_and_pathwidth_presentation.pdf |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 1280x720 | 2.21 Mbits/sec | 560.13 MB | View | Download | |
| MPEG-4 Video | 640x360 | 739.62 kbits/sec | 182.92 MB | View | Download | |
| WebM | 640x360 | 305.0 kbits/sec | 75.43 MB | View | Download | |
| iPod Video | 480x360 | 520.51 kbits/sec | 128.73 MB | View | Download | |
| MP3 | 44100 Hz | 249.77 kbits/sec | 61.68 MB | Listen | Download | |
| Auto * | (Allows browser to choose a format it supports) | |||||