The spring school consists in nine lectures presenting important developments in language theory, automata, and games.
The schedule is available there.
This lecture presents bridges between logical and algebraic descriptions of classes of regular languages of finite words. We show how to use such correspondences to derive expressiveness results, and algorithms to decide whether a given language is expressible in a given formalism. The lecture will review several such classes and describe a general framework unifying these results.
Stochastic pushdown games are infinite-state turn-based stochastic games where the states are pushdown configurations and possible moves are determined by a finite set of prefix-rewriting rules. The existing results about stochastic pushdown games concern mainly termination and reachability objectives. In the lecture we give an overview of these results and the associated proof techniques. A special attention is devoted to explaining the difference between finite-state and infinite-state games
The objective of this lecture will be to explain and to give examples and applications of the following result: "A set of regular languages is a lattice of languages if and only if it can be defined by a set of profinite equations". Connections with Ehreufeuch-Fraïssé games will also be given.
Finite state machines and automata [1] are the subject of the very rich theory of regular languages. Those formalisms are relevant at a theoretical level, as well as for their applications, such as in verification. It is clear from the origin that an similar theory that would have quantitive capapabilities would be of great interest. A general framework for such an extension has been proposed by Schützenberger [2] yieding the so called weighted automata. It gives a very appealing algebraic presentation, but usually yields to undecidability for most interesting problems.
In this lecture we will consider the problem of extending automata with counting capabilities, with a particular attention to the model of distance automata of Hashiguchi [3] and their extensions [4] and [5,6]. Those models of automata retain part of the nice theory of regular languages, in particular concerning decidability, and have at the same time counting features.
Automatic structures were introduced by Khoussainov and Nerode in 1994. Roughly speaking, a relational structure is automatic, if the elements of the structure can be coded by words in such a way that the universe is a regular language and every relation of the structure can be recognized by a synchronous multi-tape automaton. The main motivation for studying automatic structures is the fundamental fact that every automatic structure has a decidable first-order theory. In recent years, a rich theory of automatic structures started to develop, which contains both structural and more algorithmic results.
In the two talks, I will present a survey on the algorithmic theory of automatic structures. In the first lecture, we will consider decidable logics for automatic structures and their complexity. We will outline the standard automata theoretic decision algorithm for the first-order theory of an automatic structure as well as generalizations for richer logics. More efficient (elementary) algorithms for subclasses of automatic structures (e.g. automatic structures of bounded degree) will be mentioned too. The second lecture will survey recent results for the isomorphism problem for classes of automatic structures. For instance, we will show that already for automatic equivalence relations, the isomorphism problem is undecidable.
Further details can be found in the following two papers:
Stochastic games are a mathematical model of competition over discrete time. The existence and computability of the values of stochastic games is a central algorithmic question.
The lecture will present a few algorithms to compute efficiently the values of stochastic games as well as optimal or epsilon-optimal strategies for both players. The complexity of such a task depends on the class of stochastic games considered, ranging from Markov chains to Markov decision processes and two-player stochastic games, and from perfect-information stochastic games to repeated games with imperfect information.
The theory of finite monoids/semigroups has been a very successful tool for understanding regular languages of words. Two important applications are: understanding the expressive power of different logics on words, such as first-order logic, and string algorithms.
In my talk, I will describe the progress that has been made for tree
languages. Many of the important problems remain open. In particular,
it is not known if the following decision problem is decidable:
INPUT: a regular tree language, given e.g. by a tree automaton.
QUESTION: is the regular tree language definable in first-order logic?
Nevertheless, some simpler logics have been understood, and also some of the algebra is mature enough to be used in pattern matching algorithms, especially in XML. I will present some of these results, including:
No particular knowledge of topology is required. We will start from scratch with finite and infinite 2-player games with perfect information (no chance, nothing hidden). We will look into the various usual ways people play (they alternate, they pass their turns, they play several moves in a row, they even undo their previous moves...). From these game-like behaviors, we will derive the basic the topological notions. From there we will concentrate on games played on graphs, relate this to the general picture, and explain in details the implications of determinacy, and its bizarre relationship with choice.
In a second step we will use both games and topology to discuss the complexity of many omega-languages recognized essentially by automata (Büchi automata, counter automata, pushdown automata, alternating automata, tree automata, etc). As a starter we will present the Wagner hierarchy of omega-regular languages, then move on to the general Wadge hierarchy: the classification method that is the finest. We will give an overview of the many results on the Wadge complexity of omega-languages, together with the even more numerous open questions. If time permits, we will show (following a result from Arnold and Niwinski) how Wadge considerably helps proving the strictness of the semantical mu-calculus hierarchy (by simply playing a game where deciding the winner requires other games to be settled).