Tractable Probabilistic Description Logic Programs
<p>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...
| Main Author: | |
|---|---|
| Format: | Conference item |
| Published: |
Springer
2007
|
| _version_ | 1826258606636400640 |
|---|---|
| author | Lukasiewicz, T |
| author_facet | Lukasiewicz, T |
| author_sort | Lukasiewicz, T |
| collection | OXFORD |
| description | <p>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.</p> |
| first_indexed | 2024-03-06T18:36:37Z |
| format | Conference item |
| id | oxford-uuid:0b775726-741a-4911-8aa8-c142f1ec5236 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:36:37Z |
| publishDate | 2007 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:0b775726-741a-4911-8aa8-c142f1ec52362022-03-26T09:29:31ZTractable Probabilistic Description Logic ProgramsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:0b775726-741a-4911-8aa8-c142f1ec5236Department of Computer ScienceSpringer2007Lukasiewicz, T<p>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.</p> |
| spellingShingle | Lukasiewicz, T Tractable Probabilistic Description Logic Programs |
| title | Tractable Probabilistic Description Logic Programs |
| title_full | Tractable Probabilistic Description Logic Programs |
| title_fullStr | Tractable Probabilistic Description Logic Programs |
| title_full_unstemmed | Tractable Probabilistic Description Logic Programs |
| title_short | Tractable Probabilistic Description Logic Programs |
| title_sort | tractable probabilistic description logic programs |
| work_keys_str_mv | AT lukasiewiczt tractableprobabilisticdescriptionlogicprograms |