Workshop on Wadge Theory and Automata II

Date and place: June 8th, 2018 - Torino (Italy)

Organizers:

Alessandro Andretta, Filippo Cavallari, Luca Motto Ros and Matteo Viale

Location:

Department of Mathematics "Giuseppe Peano",
Palazzo Campana, via Carlo Alberto 10, Torino.

All talks will take place in Aula Magna, on the second floor.

Useful information

Program

09:30 - 10:20 - Matteo Mio

Regular Sets of Trees and Probability (Slides)

Abstract.

I will discuss some problems and results regarding probability and regular languages of infinite trees.

Nascondi.

10:30 – 11:00 - Coffee Break

11:00 - 11:50 - Olivier Finkel

Polishness of some topologies related to automata (Slides)

Abstract.

(Joint work with Olivier Carton and Dominique Lecomte) The languages of infinite words accepted by finite automata were first studied by Büchi to prove the decidability of the monadic second order theory of one successor over the integers. The Cantor topology is a very natural topology on the set $\Sigma^\omega$ of infinite words over a finite alphabet $\Sigma$ which is induced by the prefix metric. It has been used in particular to study the topological complexity of languages of infinite words accepted by various kinds of automata. However, it turned out that for several purposes some other topologies on a space $\Sigma^\omega$ are useful, for instance for studying fragments of first-order logic over infinite words. In particular, Schwarz and Staiger studied four topologies on the space $\Sigma^\omega$ which are all related to automata, and refine the Cantor topology on $\Sigma^\omega$: the Büchi topology, the automatic topology, the alphabetic topology, and the strong alphabetic topology. They proved that these four topologies are metrizable. We prove that the Büchi topology, the automatic topology, the alphabetic topology and the strong alphabetic topology are Polish, and provide consequences of this. Moreover we characterize the Wadge hierarchy on the corresponding Polish spaces. We also show that this cannot be fully extended to the case of a space of infinite labelled binary trees; in particular, the Büchi and the Muller topologies in that case are not Polish.

Nascondi.

12:00 - 12.50 - Louis Vuilleumier

The Wadge ordering over the Borel subsets of the Scott domain is not wqo (Slides)

Abstract.

The Wadge ordering - the ordering induced by continuous reductions - is the finest description of the topological complexity over the subsets of a given topological space. By mean of a game characterization of continuous reductions, Wadge and Martin proved that it is wqo over Borel subsets of zero-dimensional Polish spaces. Recently, Schlicht proved that, for Polish spaces, zero-dimensionality is actually equivalent to wqoness of the Wadge ordering over the Borel subsets. The extension of this result to the class of quasi-Polish spaces - a class of topological spaces introduced by de Brecht in the last decade as a natural class for the extension of descriptive set theory for non-metrizable spaces - is not clear. We give a first attempt to answer this question by showing that it is not wqo on the Scott domain, a universal space among the quasi-Polish spaces.

Nascondi.

13:00 – 14:30 - Lunch

14:30 - 15:20 - Jacques Duparc

Exponentiation in the Wadge Hierarchy and the Hierarchy of Norms, and Regular Tree Languages (Slides)

Abstract.

This is joint work with Riccardo Camerlo. Along the Wadge hierarchy, following Wadge's addition and Steel's (almost) multiplication, we propose an operation which behaves (almost) as an exponentiation. We use this to obtain a lower bound for the hierarchy of norms. We discuss its implications in the realm of regular tree languages.

Nascondi.

15:30 - 16:20 - Michał Skrzypczak

Games and complexity: from Banach-Mazur to automata theory (Slides)

Abstract.

Since the concepts of Banach and Mazur, many notions of "complexity" found characterisations based on games. An outstanding example are Wadge games, which literally compare topological complexity of the given pair of sets. The importance of games is also understood in automata theory, where for instance Büchi and Landweber used game semantics to solve the Church synthesis problem. Their positive solution to that problem, especially the fact of finite memory determinacy, opened new perspectives for applications of game theory in effective ways. During the talk I will present a number of examples of games relating complexity and automata theory. I will emphasise determinacy and effectiveness. I plan to conclude by some recent developments characterising certain complexity classes for regular languages of infinite trees.

Nascondi.

16:30 – 17:00 - Coffee Break

Sponsors

The workshop is generously funded by

- The Department of Mathematics "Giuseppe Peano"