|
Evènement pour le groupe Modélisation et Verification
Date | 2009-03-05 11:00-12:15 |
Titre | Modal Logics with Presburger constraints |
Résumé | In this talk, we present an extended modal logic EML with regularity constraints and
full Presburger constraints on the number of children that generalize graded modalities,
also known as number restrictions in description logics.
We show that the satisfiability problem for EML can be solved with polynomial space.
This extends a well-known and non-trivial PSPACE upper bound for graded modal logic.
Furthermore, we provide a detailed comparison with logics that contain
Presburger constraints and that are dedicated to query XML documents. As an
application, we provide a reduction from Sheaves logic SL into EML,
which allows to improve the best known upper bound for SL satisfiability.
This is a joint work with Denis Lugiez (LIF, Marseille, France).
|
Lieu | Salle 076, LaBRI, Rez-de-chaussée |
Orateur | Stéphane Demri |
Email | demri@lsv.ens-cachan.fr |
Url | LSV, Cachan, France |
Aucun document lié à cet événement. RetourRetour à l'index
| |