Evènement pour le groupe Graphes et Logique

Date 2012-01-24  11:00-12:00
TitreTopological Monadic Logic 
RésuméTopological monadic logic refers to weighted structures, i.e., structures whose elements are labelled with non-negative integers called weight. Topological monadic logic extends monadic logic with the ability to express that "there is a bound on the weights appearing on a set X" where X is a monadic variable. We consider this logic over weighted infinite words (of length omega), and we conjecture that the satisfaction of this logic is decidable (thus extending Büchi's seminal result). In this talk we introduce several equivalent formalisms for this logic, and we present results of normal forms for this logic. We describe the Borel complexity of this logic, and compare its expressiveness with the one of the logic MSO+U. Finally, we will reduce the open conjecture to some new forms of tiling problems.  
Lieusalle 76 
OrateurThomas Colcombet 
UrlCNRS, Liafa 

Aucun document lié à cet événement.

Retour à l'index