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).  
LieuSalle 076, LaBRI, Rez-de-chaussée 
OrateurStéphane Demri 
Emaildemri@lsv.ens-cachan.fr 
UrlLSV, Cachan, France 



Aucun document lié à cet événement.

Retour
Retour à l'index