Due to the Coronavirus restrictions in place in Switzerland, all the talks this semester will take place online via Zoom and the access details will be shared by e-mail. If you would like to be added to the mailing list, please contact Thomas Studer or George Metcalfe (contact details can be found in the sidebar).
|17.02.2021||16.00 - 17.00||Igor Sedlár - Czech Academy of Sciences||Changing the World, Constructively|
|24.02.2021||16.00 - 17.00||Luca Reggio - University of Oxford||Counting homomorphisms between finite structures|
|10.03.2021||16.00 - 17.00||Brett McLean - University of Nice Sophia Antipolis||Temporal logic of Minkowski spacetime|
The finite tree property of intuitionistic logic entails completeness with respect to posets where each element, seen as a possibly partial situation, is under a maximal element, seen as a possible world containing the situation. This suggests a natural semantics for intuitionistic modal logic based on posets with a binary relation on the set of maximal elements. In this semantics, truth of modal formulas in a situation is determined by looking at worlds containing the situation and worlds accessible from them. In this paper we study modal logics arising from such a semantics. A general completeness-via-canonicty result is provided and various operations on such posets including filtrations are studied. Differences with respect to intuitionistic modal logics known from the literature are discussed. In the final part a completeness result for a version of intuitionistic propositional dynamic logic based on the framework is obtained and the logic is shown to be decidable.
Lovász (1967) showed that two finite relational structures A and B are isomorphic if, and only if, the number of homomorphisms from C to A is the same as the number of homomorphisms from C to B for any finite relational structure C. Categorical generalisations of this result were proved independently in the early 1970s by Lovász and Pultr. I will present another categorical variant of Lovász' theorem and explain how it can be used, in combination with the game comonads recently introduced by Abramsky et al., to obtain homomorphism counting results in finite model theory.
This is joint work with Anuj Dawar and Tomáš Jakl.
If we wish to do temporal logic on (flat) spacetime, special relativity suggests we should use an accessibility relation that is independent of the choice of inertial frame, and that there are a limited number of ways to do this. Two possible accessibility relations are 'can reach with a lightspeed-or-slower signal' and 'can reach with a slower-than-lightspeed signal'. We focus on the resulting frames in 2D spacetime (1 space + 1 time dimension). For both frames, validity of formulas in the basic temporal language is a PSPACE-complete problem. I will describe the proofs of these results and also how those proofs can be extended to obtain results on interval logics.
This is joint work with Robin Hirsch. The lightspeed-or-slower case is due to Hirsch and Reynolds.