Stathis Delivorias
LIRMM, Montpellier
Tuesday May 11th, 2021, 16:00
Online
Abstract
Le «chase» est une famille d'algorithmes conçus pour inférer des données en utilisant des connaissances ontologiques représentées par des règles existentielles, un sous-langage de la logique du premier ordre. Dans ces bases de connaissances, l'implication est équivalente avec un homomorphisme de graphes. Nous définissons un cadre unificateur pour la spécification et l'étude des algorithmes du chase. Nous utilisons ce cadre pour expliciter et comparer les propriétés des différentes variantes du chase. Nous nous focalisons particulièrement sur le problème de la «k-saturation bornée»: k est-elle la taille maximum d'une chaîne d'applications de règles interdépendantes (où interdépendance signifie que le résultat d'une application d'une règle contribue au déclenchement de l'application suivante)? En définissant des propriétés intermédiaires, on montre que le problème de la k-saturation-bornée est décidable pour de nombreuses variantes du chase.