Tractable Probabilistic Description Logic Programs

Conference item

We propose tractable probabilistic description logic programs (or probabilistic dl-programs) for the Semantic Web, which combine tractable description logics, normal programs under the answer set semantics, and probabilities. In particular, we introduce the total well-founded semantics for probabilistic dl-programs. Contrary to the previous answer set and well-founded semantics, it is defined for all probabilistic dl-programs and all probabilistic queries. Furthermore, tight (resp., tight literal) query processing under the total well-founded semantics coincides with tight (resp., tight literal) query processing under the previous well-founded (resp., answer set) semantics whenever the latter is defined. We then present an anytime algorithm for tight query processing in probabilistic dl-programs under the total well-founded semantics. We also show that tight literal query processing in probabilistic dl-programs under the total well-founded semantics can be done in polynomial time in the data complexity and is complete for EXP in the combined complexity. Finally, we describe an application of probabilistic dl-programs in probabilistic data integration for the Semantic Web.

Authors: Lukasiewicz, T

• Publisher: Springer
• Host title: Proceedings of the 1st International Conference on Scalable Uncertainty Management‚ SUM 2007‚ Washington‚ DC‚ USA‚ October 10−12‚ 2007
• Volume: 4772
• Publication date: 2007-01-01
• ISBN: 9783540754077