Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 15 Février 2000

Logique, Complexité et données spatiales

par Luc Segoufin (INRIA Rocquencourt)

Une base de donnèe spatiale consiste en un ensemble fini d'objets spatiaux. Ceux-ci sont stockès dans la base sous un format de donnèe (semi-linèaire, semi-algèbrique, etc.) spècifiè par le systême.

Un langage de requÍte sur de telles donnèes doit assurer la reprèsentation du rèsultat dans le format de donnèe de dèpart et essayer de fournir un pouvoir d'expression aussi èleveegrave; que possible tout en garantissant une faible complexitè d'èvaluation (PTime).

Dans cet exposè on partira de la logique du premier ordre dont on prèsentera les limitations en terme de pouvoir d'expression. Puis on montrera que les langages dèrivant des extensions "classiques" du premier ordre ne vèrifient ni la condition de prèservation du format ni la faible complexitè d'èvaluation. Enfin on prèsentera des extensions du premier ordre rèpondant aux critëres prèsentès ci-dessus.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr