The logic group in Turin is pleased to announce a one-day workshop on "Wadge theory and automata". Wadge theory is an area of descriptive set theory dealing with the classification of subsets of reals in terms of their topological complexity. It has strong connections with automata theory, in particular when it comes to classifying omega-regular languages that can be recognised by different types of automata.
The workshop will consist in four talks and will be concluded by a brief discussion session outlining some open problems and future directions of the area.
Everyone is cordially invited to attend. For further information please send an email to luca.mottoros at unito.it
For organizational purposes, anyone interested in attending the workshop should send an email to luca.mottoros at unito.it before January 16th.
Alessandro Andretta, Raphaël Carroy, Luca Motto Ros and Matteo Viale
Dipartimento di Matematica "Giuseppe Peano"
Palazzo Campana, via Carlo Alberto 10, Torino, room "Sala S" (first floor).
Alberto Albano, Alessandro Andretta, Giorgio Audrito, Stefano Baratella (Trento), Gianluca Basso (Pisa), Stefano Berardi, Filippo Calderoni, Riccardo Camerlo, Felice Cardone, Gemma Carotenuto (Salerno), Raphaël Carroy, Filippo Cavallari, Anupam Das (Lyon), Ugo de' Liguoro, Jacques Duparc (Lausanne), Alessandro Facchini (IDSIA, Switzerland), Olivier Finkel (Paris), Kevin Fournier (Lausanne), Fiorella Guichardaz (Freiburg), Gabriele Gullà (Roma), Giorgio Laguzzi (Freiburg), Bruno Li Marzi, Luca Motto Ros, Hugo Nobrega (Amsterdam), Yann Pequignot (Lausanne and Paris), Edoardo Rivello, Luca Roversi, Victor Selivanov (Novosibirsk), Silvia Steila, Sam van Gool (Milano), Matteo Viale, Domenico Zambella
Under some determinacy hypothesis, we give a direct proof of the correspondence between the Wadge hierarchy of the Baire space restricted to the non-self-dual degrees and the conciliatory hierarchy obtained by first adding the finite sequences to the Baire space, and then symmetrizing the game theoretical tools involved. Since the study of the Wadge hierarchy of the Baire space can be reduced to the study of its non-self-dual degrees only, we thus demonstrate that the study of the Wadge hierarchy is equivalent to the study of the conciliatory hierarchy. We show moreover that the conciliatory hierarchy is induced by reductions by relatively continuous relations on the space of finite and infinite sequences of integers, endowed with the prefix topology.
In recent years, a lot of effort has been put by the "Logic in Computer Science" research community in the aim of understanding the main logic formalisms used for describing properties of trees. But what is meant by "understanding a logic"? The approach we assume here follows the slogan that to understand a logic means to dispose of an effective characterization of it, or, said otherwise, to solve the associated definability problem: given a regular tree language L, is it possible to decide whether there is a formula of the considered logic defining L?
If this is the intended meaning, then, contrary to the case of words, very few logics on trees are understood.
In this talk we are interested in two versions of the definability problems: the Rabin-Mostowski index problem and the Wadge problem for regular languages of infinite trees.
The former asks, given as input a regular tree languages L and an index (i,k), whether there is a parity automaton of index (i,k) recognizing L. This problem clearly depends on the mode of the chosen class of automata: deterministic, non-deterministic, alternating, et cetera. We thus speak of the deterministic / non-deterministic / alternating index problem. The Wadge problem asks, given as input a regular tree languages L and an ordinal A, whether the Wadge degree of L is A.
From the perspective of these two problems, there are two main reasons for the lack of understanding of logics on infinite trees: on one hand, there is no canonical representation of a regular language of infinite trees, and on the other hand, topologically, regular tree languages are very complicated.
Except for the deterministic case, both the index and the Wadge problems have at the moment no known solutions.
In my talk I will present two recent advances done in collaboration with Filip Murlak, Michal Skrzypczak an Henryk Michalewski.
We develop the theory of omega-regular k-partitions (for arbitrary k>1) that extends the theory around the Wagner hierarchy of regular omega-languages. In particular, we characterize the structure of Wadge degrees of omega-regular k-partitions, prove the decidability of any level of the corresponding hierarchy, establish coincidence of the reducibilities by continuous functions and by functions computed by finite automata on the omega-regular k-partitions.
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 of omega-languages accepted by 1-counter Büchi
automata (or by 2-tape 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, or of an infinitary rational relation accepted by a 2-tape Büchi automaton,
is not determined by the axiomatic system
ZFC. In particular, there is a 1-counter Büchi automaton A (respectively, a 2-tape Büchi
automaton B) and two models V1 and V2 of ZFC such that the omega-language L(A)
(respectively, the infinitary rational relation L(B)) is Borel in V1 but not in V2.
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted
by real-time 1-counter Büchi automata (or by 2-tape Büchi automata) is equivalent to
the determinacy of (effective) analytic Gale-Stewart games which is known to be a large
cardinal assumption. Using some results of set theory we prove that one can effectively
construct a 1-counter Büchi automaton (respectively, a 2-tape Büchi automaton)
A such that: (1) There exists a model of ZFC in which Player 1 has a winning strategy
in the Gale-Stewart game G(L(A)); but the winning strategies cannot be recursive and not
even hyperarithmetical. (2) There exists a model of ZFC in which the Gale-Stewart game
is not determined.
We also prove that the determinacy of Wadge games between two players in charge of
omega-languages accepted by real-time 1-counter Büchi automata
(or by 2-tape Büchi automata) is equivalent to the effective analytic determinacy, and
thus is not provable in ZFC.
In the days preceeding the workshop there will be two seminars addressed to students and non-experts in the field in which we will give a short presentation of the basics of Wadge theory and automata theory.
- Monday January 26th, 2015, 14:00-17:00: Seminar on Wadge theory.
Abstract.
We will give a brief and self-contained introduction to the Wadge theory. After giving all the relevant definitions, we will show how certain two players infinite games on the natural numbers can be used to fully determine the Wadge hierarchy on the Baire space and on some other spaces relevant to automata theory, e.g. the space of infinite words on a given finite alphabet.
- Tuesday January 27th, 2015, 14:00-17:00: Seminar on automata theory.
Abstract.
We will give a short glimpse in the rich and profuse field of automata theory. Our aim is to give at least the basic definitions for the workshop. No previous knowledge in automata theory is needed. The tutorial will be in two parts.
In the first part we present classical matters in automata theory: automata on finite words, Büchi and Muller automata, links with Monadic Second Order logic.
In the second part we give definitions of some special classes of automata: Büchi automaton with counters, parity and tree automata.
Both seminars will be held at Dipartimento di Matematica "Giuseppe Peano", Palazzo Campana, via Carlo Alberto 10, Torino, room "Sala S" (same location of the workshop).
We will make available modest travel awards to graduate or recent Ph.D. students so that they may attend the workshop. To be considered for a travel award, please send a letter of application by e-mail at the address luca.mottoros at unito.it.
The application letter should be brief (preferably one page) and should include: (1) your name; (2) your home institution; (3) the name of your supervisor; (4) a one-paragraph description of your studies and work in logic, and a paragraph indicating why it is important to attend the meeting; (5) your estimate of the travel expenses you will incur.
The deadline for the submission of a letter of application is 09.01.2014.The workshop is generously funded by
- Department of Mathematics "Giuseppe Peano" - University of Turin
- PRIN 2012 "Modelli e insiemi" (PI: Carlo Toffalori)
- San Paolo junior PI grants 2012 "New Perspectives On The Nature Of Infinity" (PI: Matteo Viale)
- Young Researchers Program Rita Levi Montalcini 2012 "New advances in Descriptive Set Theory" (PI: Luca Motto Ros)
and is sponsored by AILA - Associazione Italiana di Logica e sue Applicazioni.