COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > The Expressive Power of CSP Quantifiers

## The Expressive Power of CSP QuantifiersAdd to your list(s) Download to your calendar using vCal - Lauri Hella, Tampere University
- Thursday 29 September 2022, 14:00-15:00
- SS03.
If you have a question about this talk, please contact Jamie Vicary. A generalized quantifier Q is called a CSP -quantifier if its defining class consists of all structures that can be homomorphically mapped to a fixed finite template structure. For all positive integers n>1 and k, we define a pebble game that characterizes equivalence of structures with respect to the extension of the infinitary k-variable logic by all unary quantifiers and the class C_n of all CSP quantifiers with template structures that have at most n elements. Using these games we prove that for every n>1 there exists a CSP -quantifier with template of size n+1 which is not definable in finite variable logic with all unary quantifiers and quantifiers in C_n. The proof of this result is based on a new variation of the well-known Cai-Fürer-Immerman construction. This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Cambridge talks
- Computing and Mathematics
- Department of Computer Science and Technology talks and seminars
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- SS03
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsMp3 Music Download Molecules and genes in Alzheimer's Whiston Society## Other talksJCTS PRESENTATIONS Coffee Recent Developments in Spectral Theory of Focusing NLS Soliton Gases: Average Densities, Fluxes and Periodic Gases Networking Reception Introduction Transport Phenomena in Liquid Metal Batteries |