Logique, automates, algèbre et jeux
Mercredi 17 décembre 2014, 10 heures 30, 4068
Stefan Göller (LSV) Equivalence checking of infinite state systems: A couple of lower bounds
Logique, automates, algèbre et jeux
Mercredi 3 décembre 2014, 10 heures 30, 4068
Thomas Colcombet (LIAFA) Stabilization monoids and cost functions
Logique, automates, algèbre et jeux
Mercredi 19 novembre 2014, 10 heures 30, 4068
Thomas Colcombet (LIAFA) Decidability of Boundedness and Limitedness
In this second part, we will establish the decidability of this second problem, following the ideas of Leung, Simon, and Kirsten.
Logique, automates, algèbre et jeux
Mercredi 5 novembre 2014, 10 heures 30, 4068
Thomas Colcombet (LIAFA) The star-height problem and its link to boundedness and limitedness
The goal of the first session is to present the famous (restricted) star-height problem, and show the first steps toward its resolution. The question is the following: given a regular language L and a non-negative integer k, can we decide whether L can bee represented as a regular expression of star-height (i.e., nesting of Kleene stars) at most k. This problem has been open for 25 years unit Hashiguchi provided a proof in a series of four paper, between 81 and 88. This proof is notoriously difficult, and the presentation here will be based on the ideas in the more modern, and much simpler, proof of Kirsten (2005).
The idea behind both these proofs is to reduce the original problem to a question of existence of bounds for a function computed by some specific forms of automata (distance automata, nested-distance desert automata, B-automata, …). This idea goes much beyond the scope of the star-height problem, and I will try to convey this idea through several examples.
Logique, automates, algèbre et jeux
Jeudi 10 avril 2014, 10 heures 30, 2014
David Xiao (LIAFA) Une introduction aux graphes expandeurs
Dans cet exposé nous présenterons les graphes expandeurs, leur(s) définition(s), quelques lemmes structurels fondamentaux, et quelques exemples de leur utilisation dans la dérandomisation. Nous esquisserons également la construction basée sur le produit zigzag.
Logique, automates, algèbre et jeux
Jeudi 27 mars 2014, 10 heures 30, 2014
Michael Vanden Boom (Oxford university) Automata characterizations of WMSO
In this talk, I will sketch the proofs showing the equivalence of WMSO and a form of automata called weak alternating automata. I will also prove Rabin’s characterization of WMSO: a language is weakly definable iff the language and its complement are recognizable by nondeterministic Büchi automata.
I will conclude by describing connections with recent work (joint with Thomas Colcombet, Denis Kuperberg, and Christof Löding) showing that given a Büchi automaton as input, it is decidable whether the language is definable in WMSO.
Logique, automates, algèbre et jeux
Jeudi 13 mars 2014, 10 heures 30, 2014
Olivier Serre (LIAFA) Rabin theorem
Hence, the structure of the talk will be as follows:
I will assume no specific knowledge on automata nor games for that talk.
Logique, automates, algèbre et jeux
Samedi 1 mars 2014, 10 heures 30, 2014
Nathanaël Fijalkow (LIAFA) Positional determinacy part II
I will highlight the differences between the two approaches, and the applications of both techniques. In particular, I will explain why backward approaches naturally induce determinization procedures for automata over infinite words.
The talk will be self-contained, and in particular I will quickly recall all required definitions at the beginning.
Logique, automates, algèbre et jeux
Jeudi 6 février 2014, 10 heures 30, 2014
Thomas Colcombet (LIAFA) Positional determinacy part I
This is in preparation to the seminars after the holidays, that will aim at presenting the results on the monadic theory of the infinite binary tree.