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) > A compositional account of Herbrand's theorem via concurrent games

## A compositional account of Herbrand's theorem via concurrent gamesAdd to your list(s) Download to your calendar using vCal - Pierre Clairambault, ENS Lyon
- Friday 18 November 2016, 14:00-15:00
- SS03.
If you have a question about this talk, please contact Dominic Mulligan. NOTE NON-STANDARD ROOM BOOKING Herbrand’s theorem, often regarded as a cornerstone of proof theory, exposes some of the constructive content of classical logic. In its simplest form, it reduces the validity of a first-order purely existential formula ∃x.φ(x) (with φ quantifier-free) to that of a finite disjunction φ(t₁) ∨ … ∨ φ(tₙ). More generally, it gives a reduction of first-order validity to propositional validity, by understanding the structure of the assignment of first-order terms to existential quantifiers, and the causal dependency between quantifiers. In this talk, I will show that Herbrand’s theorem in its general form can be elegantly stated as a theorem in the framework of concurrent games. The causal structure of concurrent strategies, paired with annotations by first-order terms, is used to specify the dependency between quantifiers. Furthermore concurrent strategies can be composed, yielding a compositional proof of Herbrand’s theorem, simply by interpreting classical sequent proofs in a well-chosen denotational model. I assume no prior knowledge of Herbrand’s theorem or concurrent games. This is joint work with Aurore Alcolei, Martin Hyland and Glynn Winskel. 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)
- Computer Laboratory talks
- Computing and Mathematics
- 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 lists1 and 1/2 APDE days BBMS Engineering Design Centre Seminars## Other talksNeurodevelopment disorders of genetic origin – what can we learn? Imaging surfaces with atoms PROFESSIONAL REGISTRATION WORKSHOP Big and small history in the Genizah: how necessary is the Cairo Genizah to writing the history of the Medieval Mediterranean? Eukaryotic cell division and its origins |