Possibilistic ALC description logic for operational information systems : theory, algorithm and applications
Operational Information Systems (OIS) face challenges to manage an increasing amount of heterogeneous and uncertain data. To tackle this problem, we consider the ALC Description Logic (DL) formalism and we provide a possibilistic extension of the tableau algorithm called possibilistic tableau algorithm. In this thesis, we provide contributions at three levels (a theorical one, an algorithmic one and an OIS context-based one) for this procedure dedicated to computing the inconsistency degree of a knowledge base. From a theorical point of view, we provide possibilistic completion rules to apply syntaxical rewrittings on formulas while managing their corresponding certainty degrees. We prove their local correctness and we provide rules for adding newly generated formulas to the knowledge base. We analyze the algorithmic properties, i.e. the soundness and the completeness of the procedure, in the light of the possibilistic framework. From an algorithmic point of view, we take into account the problem of an efficient running of the possibilistic tableau algorithm and we provide a cutting tree strategy on the completion tree based on an heuristic identification of the relevant subset of formulas to be processed. We explain why this optimization does not impact the algorithmic properties and we provide the complete description of the algorithm and its implementation. From an OIS context-based point of view, we argue on the improvements of the proposed algorithm with three kinds of operational services and we instance its suitability by means of two examples, one illustrating the fusion of elementary information and the other one illustrating the way our algorithm is useful to interpret the situation awarness.
Defence : 03/05/2010 - 10h - Site Passy-Kennedy - salle 549 Jury members : Rapporteurs :
Mme Marie-Christine Rousset
Mr Salem Benferhat