## SSLPS Annual Meeting 2015

# Computer Science meets Descriptive Set Theory

**Lausanne, 20-21 November 2015**

Room: **Internef, 233** (metro station UNIL-Dorigny)

### Friday

**13:20****Olivier Finkel **(IMJ-PRG Paris)

### (Descriptive) Set Theory and Automata Theory

abstract:

*The theory of automata reading infinite words, which is closely related to infinite games, is a rich theory which is used for the specification and verification of non-terminating systems. We prove that the Wadge hierarchy, which is a great refinement of the Borel hierarchy, of omega-languages accepted by 1-counter Büchi automata is equal to the Wadge hierarchy of omega-languages accepted by Büchi Turing machines, which forms the class of effective analytic sets. Moreover the topological complexity of an omega-language accepted by a 1-counter Büchi automaton is not determined by the axiomatic system ZFC. In particular, there is a 1-counter Büchi automaton A and two models V_1 and V_2 of ZFC such that the omega-language L(A) is Borel in V_1 but not in V_2.*

**14:25****Michał Skrzypczak** (University of Warsaw)

### An automata-theoretic hierarchy inside **Δ**^{1}_{2}

^{1}

_{2}

abstract:

*Rabin automata on infinite trees is a tool to solve decision problems involving infinite computations. They induce a hierarchy of sets in Δ ^{1}_{2}, which goes far beyond analytic sets. The hierarchy is related to inductive definability, and also to R-sets of Kolmogorov.*

**15:30**

* coffee-break *

**16:00**

**Raphaël Carroy** (University of Turin)

### Classifying functions

Abstract:We examine a notion of reduction between functions, the strong Weihrauch reducibility, also called continuous reducibility. After discussing the relevance of other quasi-orders existing in the literature, We begin the analysis of continuous functions between zero-dimensional Polish spaces with respect to continuous reducibility.

**17:05**

**Yann Pequignot**(University of Lausanne)

### A Wadge hierarchy for second countable spaces

Abstract:

We define a notion of reducibility for subsets of a second countable T0 topological space based on, so called, admissible representations. It coincides with Wadgereducibility on zero dimensional spaces. However in virtually every second countable T0 space, it yields a hierarchy on Borel sets, namely it is wellfounded and antichains are of length at most 2. It thus differs from the Wadge reducibility in many important cases, for example on the real line or the Scott Domain.

**18:10**

*Bernays prize awarding ceremony*

**18:15**

**Bill Wadge **(University of Victoria)

*And the Rest is History (informal talk by Bill Wadge about
Descriptive Set Theory in California around the 70’s and the origins of
the Wadge hierarchy)*

**18:45**

*SSLPS general assembly meeting*

*SSLPS general assembly meeting*

**19:00**

### Saturday

**10:00****Takako Nemoto** (Japan Advanced Institute of Science and Technology)

### Determinacy of Wadge classes and subsystems of second order arithmetic_{}

_{}

abstract**:**

*In [1], the class of games in second order arithmetic corresponding to Wadge classes are given and it was proved that the determinacy of such classes in low level of arithmetical hierarchy characterize almost all known subsystems of second order arithmetic. In this talk, we review the results in [1] and introduce several recent results.[1] Takako Nemoto, Determinacy of Wadge classes and subsystems of second order arithmetic, Mathematical Logic Quarterly, Volume 55, Issue 2, February 2009, pp. 154 - 176.*

**11:05****Alessandro Andretta** (University of Turin)

### Descriptive set theory and the density point property

abstract**:**

we present a few results that lie on the thin line that separates descriptive set theory from measure theory theory and real analysis. This is part of an ongoing project with Riccardo Camerlo and Camillo Costantini.

**12:10**

**lunch**

**13:30****Henryk Michalewski** (University of Warsaw)

### Crossing the line between decidability and undecidability with

help of quantifiers

**14:35**

abstract**:**

The monadic second order theory of the binary tree is decdable thanks to Rabin's theorem proved half a century ago. One can try to improve on this result considering stronger logics which allow to quantify not only over subsets of the binary tree but also enforce that the set of witnesses of the second order quantification is large, for example in terms of a sigma-ideal. I will discuss few such

attempts, including the ideal of sets of the first Baire category and the ideal of sets of measure 0.

One notion of largness led to a quite generic undecidability result which depends on the assumption V=L. This inspired another project which I am plannning to discuss - in terms of reverse mathematics, establish how much of game determinacy is needed to get Rabin's theorem.

**15:40**

In the early 1960’s, the seminal work of J. R. Büchi established the decidability of the second order monadic logic with one successor by mean of finite automata reading words of infinite length. Since then, computer science has been more and more involved not just with discrete objects, but also with infinite ones. For instance, reactive computations are often modelled as infinite words or infinite trees, giving rise to word languages as well as tree languages. From a topological viewpoint these languages are all homeomorphic to certain subsets of reals that lie in the scope of Descriptive Set Theory. It turns out that the methods of Descriptive Set Theory shed an intriguing light on these models of computation. Even for machines as simple as automata or counter-automata, the whole picture is striking and it sometimes involves much higher infinite objects such as large cardinal hypotheses to make it precise.