~~NOCACHE~~
/* DO NOT EDIT THIS FILE             */

[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Jeudi 20 décembre 2012, 10 heures 30, -\\
**Sam Van Gool** (LIAFA) //A topological proof of Gödel’s completeness theorem for first-order logic//
<button type="link" size="xs" collapse="b23-3816">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3816" collapsed="true">
<well size="sm">
In the fifties of the previous century, Rasiowa and Sikorski gave a topological proof of Gödel’s completeness theorem for first-order logic. Their proof ultimately relies on the Baire category theorem, which is mainly known for its powerful applications in real and functional analysis. Therefore, the application of Baire’s theorem to prove this fundamental result in logic is a surprising and interesting one. The main goal of this talk will be to give an exposition of this elegant topological proof by Rasiowa and Sikorski.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Jeudi 13 décembre 2012, 10 heures 30, -\\
**Colin Riba** (ENS Lyon) //A Model Theoretic Proof of Completeness of an Axiomatization of Monadic Second-Order Logic on Infinite Words//
<button type="link" size="xs" collapse="b23-3817">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3817" collapsed="true">
<well size="sm">
We discuss the completeness of an axiomatization of Monadic Second-Order Logic (MSO) on infinite words (or streams). By using model-theoretic tools, we give an alternative proof of D. Siefkes’ result that a fragment with full comprehension and induction of second-order Peano’s arithmetic is complete w.r.t. the validity of MSO-formulas on streams. We rely on Feferman-Vaught Theorems and the Ehrenfeucht-Fraissé method for Henkin models of second-order arithmetic. Our main technical contribution is an infinitary Feferman-Vaught Fusion of such models. We show it using Ramseyan factorizations similar to those for standard infinite words. We also discuss a Ramsey’s theorem for MSO-definable colorings, and show that in linearly ordered Henkin models, Ramsey’s theorem for additive MSO-definable colorings implies Ramsey’s theorem for all MSO-definable colorings.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Jeudi 14 juin 2012, 10 heures 30, -\\
**Frédéric Magniez** (LIAFA) //An Introduction to Communication Complexity//
<button type="link" size="xs" collapse="b23-3818">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3818" collapsed="true">
<well size="sm">
We will give a self-content course on the basics of Communication Complexity together with simple and elegant applications for proving lower bounds in different computational models. For instance, we will give a space time tradeoff for recognizing a palindrome on a Turing machine.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Jeudi 31 mai 2012, 10 heures 30, -\\
**Thomas Colcombet** (LIAFA) //The collapse of monadic second order logic over countable linear orderings//
<button type="link" size="xs" collapse="b23-3819">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3819" collapsed="true">
<well size="sm">
This talk corresponds to a joint work with Olivier Carton and Gabriele Puppis and provides a prolongation of the previous seminar. The subject wil be the algebraic approach to monadic second order logic over infinite words. We will in particular show how this notion of recognition is equivalent to the logic. This techniques provide at the same time a collapse of the logic to the one with only one alternation of monadic quantifiers.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Jeudi 10 mai 2012, 10 heures 30, -\\
**Thomas Colcombet** (LIAFA) //The monadic theory of orderings//
<button type="link" size="xs" collapse="b23-3820">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3820" collapsed="true">
<well size="sm">
In this talk, we present the aproaches of Rabin (69) and Shelah (75) for deciding the monadic theory of the rationals with order.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Jeudi 3 mai 2012, 10 heures 30, -\\
**Michel De Rougemont** (LIAFA) //Games for Monadic Σ11 (EMSO) and probabilistic methods//
<button type="link" size="xs" collapse="b23-3821">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3821" collapsed="true">
<well size="sm">
I’ll survey the classical Ehrenfeucht-Fraisse and Ajtai-Fagin games for this Logic. I’ll explain the role of the probabilistic method to prove that s,t-connexity is not Σ11 (EMSO) on graphs, using the Ajtai-Fagin games.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Jeudi 12 avril 2012, 10 heures 30, -\\
**Olivier Carton** (LIAFA) //Kamp's theorem//
<button type="link" size="xs" collapse="b23-3822">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3822" collapsed="true">
<well size="sm">
Kamp’s theorem states the equivalence between temporal logics and temporal logics with past operators over complete linear orderings.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Lundi 26 mars 2012, 10 heures 30, submarine\\
**Achim Blumensath** (LIAFA) //Stability theory//
<button type="link" size="xs" collapse="b23-3823">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3823" collapsed="true">
<well size="sm">
-
</well>
</collapse>