Logic, automata, algebra and games Thursday December 20, 2012, 10:30AM, - Sam Van Gool (LIAFA) A topological proof of Gödel’s completeness theorem for first-order logic 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. Logic, automata, algebra and games Thursday December 13, 2012, 10:30AM, - Colin Riba (ENS Lyon) A Model Theoretic Proof of Completeness of an Axiomatization of Monadic Second-Order Logic on Infinite Words 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. Logic, automata, algebra and games Thursday June 14, 2012, 10:30AM, - Frédéric Magniez (LIAFA) An Introduction to Communication Complexity 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. Logic, automata, algebra and games Thursday May 31, 2012, 10:30AM, - Thomas Colcombet (LIAFA) The collapse of monadic second order logic over countable linear orderings 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. Logic, automata, algebra and games Thursday May 10, 2012, 10:30AM, - Thomas Colcombet (LIAFA) The monadic theory of orderings In this talk, we present the aproaches of Rabin (69) and Shelah (75) for deciding the monadic theory of the rationals with order. Logic, automata, algebra and games Thursday May 3, 2012, 10:30AM, - Michel De Rougemont (LIAFA) Games for Monadic Σ11 (EMSO) and probabilistic methods 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. Logic, automata, algebra and games Thursday April 12, 2012, 10:30AM, - Olivier Carton (LIAFA) Kamp's theorem Kamp’s theorem states the equivalence between temporal logics and temporal logics with past operators over complete linear orderings. Logic, automata, algebra and games Monday March 26, 2012, 10:30AM, submarine Achim Blumensath (LIAFA) Stability theory -