Vous êtes ici: UNIL > HEC Inst. > HEC App. > LOGIQUE > recent_news > SSLPS Annual Meeting 2015
Français | English

SSLPS Annual Meeting 2015

Computer Science meets Descriptive Set Theory

Lausanne, 20-21 November 2015

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


Olivier Finkel (IMJ-PRG Paris)

(Descriptive) Set Theory and  Automata Theory


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.

Michał Skrzypczak (University of Warsaw)

An automata-theoretic hierarchy inside Δ12


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




Raphaël Carroy (University of Turin)

Classifying functions

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.
Yann Pequignot (University of Lausanne)

A Wadge hierarchy for second countable spaces


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.


Bernays prize awarding ceremony


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)


SSLPS general assembly meeting



Takako Nemoto (Japan Advanced Institute of Science and Technology)

Determinacy of Wadge classes and subsystems of second order arithmetic


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.

Alessandro Andretta (University of Turin)

Descriptive set theory and the density point property


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.



Henryk Michalewski (University of Warsaw)

Crossing the line between decidability and undecidability with
help of quantifiers



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.


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.

Internef - CH-1015 Lausanne - Suisse - Tél. +41 21 692 33 00 - Fax +41 21 692 33 05