Evènement pour le groupe Graphes et Logique

Date 2012-10-16  11:00-12:00
TitreA Model Theoretic Proof of Completeness of an Axiomatization of Monadic Second-Order Logic on Infinite Words 
Résumé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-Fraïssé 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.  
OrateurColin Riba 
UrlLIP, ENS Lyon 

Aucun document lié à cet événement.

Retour à l'index