Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog
We propose a novel, type-elimination-based method for standard reasoning in the description logic SHIQbs extended by DL-safe rules. To this end, we first establish a knowledge compilation method converting the terminological part of an ALCIb knowledge base into an ordered binary decision diagram (OB...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2012
|
| _version_ | 1826296947277824000 |
|---|---|
| author | Rudolph, S Krötzsch, M Hitzler, P |
| author_facet | Rudolph, S Krötzsch, M Hitzler, P |
| author_sort | Rudolph, S |
| collection | OXFORD |
| description | We propose a novel, type-elimination-based method for standard reasoning in the description logic SHIQbs extended by DL-safe rules. To this end, we first establish a knowledge compilation method converting the terminological part of an ALCIb knowledge base into an ordered binary decision diagram (OBDD) that represents a canonical model. This OBDD can in turn be transformed into disjunctive Datalog and merged with the assertional part of the knowledge base in order to perform combined reasoning. In order to leverage our technique for full SHIQbs, we provide a stepwise reduction from SHIQbs to ALCIb that preserves satisfiability and entailment of positive and negative ground facts. The proposed technique is shown to be worst-case optimal w.r.t. combined and data complexity. ©S. Rudolph, M. Krötzsch, and P. Hitzler. |
| first_indexed | 2024-03-07T04:24:09Z |
| format | Journal article |
| id | oxford-uuid:cc0ab043-c1f0-45be-8a2d-7f80b60d69e4 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:24:09Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:cc0ab043-c1f0-45be-8a2d-7f80b60d69e42022-03-27T07:19:00ZType-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalogJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:cc0ab043-c1f0-45be-8a2d-7f80b60d69e4EnglishSymplectic Elements at Oxford2012Rudolph, SKrötzsch, MHitzler, PWe propose a novel, type-elimination-based method for standard reasoning in the description logic SHIQbs extended by DL-safe rules. To this end, we first establish a knowledge compilation method converting the terminological part of an ALCIb knowledge base into an ordered binary decision diagram (OBDD) that represents a canonical model. This OBDD can in turn be transformed into disjunctive Datalog and merged with the assertional part of the knowledge base in order to perform combined reasoning. In order to leverage our technique for full SHIQbs, we provide a stepwise reduction from SHIQbs to ALCIb that preserves satisfiability and entailment of positive and negative ground facts. The proposed technique is shown to be worst-case optimal w.r.t. combined and data complexity. ©S. Rudolph, M. Krötzsch, and P. Hitzler. |
| spellingShingle | Rudolph, S Krötzsch, M Hitzler, P Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog |
| title | Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog |
| title_full | Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog |
| title_fullStr | Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog |
| title_full_unstemmed | Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog |
| title_short | Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog |
| title_sort | type elimination based reasoning for the description logic shiqbs using decision diagrams and disjunctive datalog |
| work_keys_str_mv | AT rudolphs typeeliminationbasedreasoningforthedescriptionlogicshiqbsusingdecisiondiagramsanddisjunctivedatalog AT krotzschm typeeliminationbasedreasoningforthedescriptionlogicshiqbsusingdecisiondiagramsanddisjunctivedatalog AT hitzlerp typeeliminationbasedreasoningforthedescriptionlogicshiqbsusingdecisiondiagramsanddisjunctivedatalog |