|
|
|
Intitulé:
Topological Monadic Logic du groupe Graphes et Logique
|
Date | 2012-01-24 11:00-12:00 |
Titre | Topological 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. |
Lieu | salle 76 |
Orateur | Thomas Colcombet |
Email | thomas.colcombet@liafa.jussieu.fr |
Url | CNRS, Liafa |
Aucun document lié à cet événement. RetourRetour à l'index
| |