Séminaires : Séminaire de Logique Lyon-Paris

Equipe(s) : lm,
Responsables :O. Finkel, A. Khélif, S. Rideau, T. Tsankov, A. Vignati
Email des responsables :
Salle : Zoom ID: 824 8220 9628; s'inscrire à la liste ou contacter silvain.rideau@imj-prg.fr pour le mot de passe.
Adresse :
Description

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion


Orateur(s) Michał Skrzypczak - Université de Varsovie,
Titre Measure theory and Monadic Second-order logic over infinite trees
Date17/06/2020
Horaire16:00 à 17:15
Diffusion
Résume

Monadic Second-order (MSO) logic is a well-studied formalism featuring many decision procedures and effective transformations. It is the fundamental logic considered in automata theory, equivalent to various other ways of defining sets of objects. In this talk, I will speak about the expressive power of MSO over infinite binary trees (i.e. free structures of two successors) - the theory from the famous Rabin's decidability result.

The goal of the talk is to survey recent results about measure properties of MSO-definable sets of infinite trees. First, I will argue that these sets are indeed measurable (which is not obvious, as there exist non-Borel sets definable in MSO). Then I will move to the question of our ability to compute the measure of the set defined by a given formula. Although the general question is still open (and seems to be demanding), I will speak about decidability results for fragments of MSO, focusing on the so-called weak-MSO.

SalleZoom ID: 824 8220 9628; s'inscrire à la liste ou contacter silvain.rideau@imj-prg.fr pour le mot de passe.
Adresse
© IMJ-PRG