Part 1: Logic and Its Many Faces

Prof Glynn Winskel (Queen Mary University of London)

From Concurrent Games to Gödel’s Dialectica Interpretation (slides)

Abstract: Computation today is highly distributed and interactive. Event structures represent computation in terms of causal dependency and conflict relations on events; the relations make precise the sense in which events can occur concurrently (independently, in parallel). By redeveloping games in sufficient generality, as event structures, interactive computation becomes a strategy and its type a game; the dichotomy between a system and its environment is caught in the distinction between Player and Opponent moves. A surprise in the development of concurrent games has been that several, seemingly disparate, historical approaches in logic and computation reappear as special cases. One special case is a concurrent-games reading of Gödel’s Dialectica Interpretation of arithmetic in a higher-order functional language. 

Dr Nikos Tzevelekos (Queen Mary University of London)

Automata and Logics for Infinite Alphabets (slides)

Abstract: While automata theory has traditionally been based on the model of an abstract machine operating on a finite alphabet of input symbols, this assumption can be limiting for a range applications where value domains cannot be reasonably bounded: from XML model-checking, to process modelling and the verification of name-generating code. This has recently lead to a surge of interest in automata over infinite alphabets, thus opening up a world of open problems and new results. The talk will look into these exciting developments with a specific focus on register automata and their equivalence properties.

Part 2: Logic and Learning

Dr Søren Riis (Queen Mary University of London)

Logic, Games & AI (slides)

Abstract: We explore why artificial intelligence, which can master complex games like Go, Shogi and Chess through self-learning, sometimes struggles with simple games like NIM, a simple children's game with a precise mathematical solution. We show how AI can dramatically improve by using recent game history rather than isolated positions. 

The main result allows us to identify two fundamentally distinct modes of reasoning: one based on pattern recognition and another rooted in infinite reasoning. This distinction helps us understand the nature of thinking in different contexts.

Dr Vladislav Ryzhikov (Birkbeck, University of London)

Reverse Engineering and Learning of Temporal Logic Queries (slides)

Abstract: In reverse engineering of database queries, one aims to learn a query from two given sets of examples where answers are supposed to be positive and negative. The query can then be used to find explanation of the answers and non-answers, and also as a classifier for new data instances.  We start by formulating a general separation problem in the setting where the queries are temporal logic formulas, and the data instances are finite sets of temporal facts. We present a number of examples to motivate the problem. We present our recently obtained results related to the computational complexity of computing separating linear temporal logic (LTL) queries.

Part 3: Logic and Graphs

Dr Sandra Kiefer (University of Oxford)

Compact Representations of Graphs in Logic

Abstract: Given an arbitrary graph, how difficult is it to describe the graph up to isomorphism? What is the complexity of a simplest first-order sentence that defines the graph? How many variables are required or sufficient to define the graph in first-order logic? And how can we find such a compact sentence algorithmically? My talk will provide answers to these questions with techniques inspired by classical theoretical results on the connections between logics and algorithms as well as by methods from practical isomorphism solvers. It will reveal counting as an effective tool to save variables in a defining formula.

Dr Marc Roth (Queen Mary University of London)

The Weisfeiler-Leman Dimension of Pattern Counting Problems (slides)

Abstract: Weisfeiler-Leman (WL) equivalence is a famous heuristic for graph isomorphism: Two graphs G and H are called k-WL-equivalent if they cannot be distinguished by the k-dimensional WL-algorithm, which is equivalent to G and H satisfying the same sentences in the k-variable fragment of first-order logic with counting quantifiers (Cai, Fürer, Immerman 1992). For a function f from graphs to rational numbers, the WL-dimension of f is the minimum k, such that f cannot distinguish k-WL-equivalent graphs. In this talk, we explore the connection between the WL-dimension and the computational complexity of pattern counting problems, that is, functions that map an input graph G to the number of occurrences of a pre-specified substructure, such as triangle counting. We will find that, under standard assumptions from fine-grained complexity theory, the WL-dimension of such a pattern counting problem f is almost precisely the minimum positive integer c, such that f can be solved in time O(|V(G)|^{c+1}). 

Part 4: Logic and Paradoxes (a science outreach session)

Dr Paulo Oliva (Queen Mary University of London)

Self-reference and Paradoxes: To Infinity and Back! (slides)

Abstract: Ever since the Greeks discovered that self-reference can lead to paradoxes (with the sentence “All Cretans are liars”, proclaimed by a Cretan), the fascination with self-referential objects has occupied the minds of artists, philosophers, mathematicians, logicians and computer scientists. In this lecture we will go through some other surprising examples of self-reference, including in language, arts and computing, and discuss how these can lead to puzzling paradoxes and to amazing inventions — such as computers!