Pushing the boundaries of tractable ontology reasoning
We identify a class of Horn ontologies for which standard reasoning tasks such as instance checking and classification are tractable. The class is general enough to include the OWL 2 EL, QL, and RL profiles. Verifying whether a Horn ontology belongs to the class can be done in polynomial time. We sh...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Springer International Publishing
2014
|
| Subjects: |
| _version_ | 1826317683708133376 |
|---|---|
| author | Carral, D Feier, C Grau, BC Hitzler, P Horrocks, I |
| author_facet | Carral, D Feier, C Grau, BC Hitzler, P Horrocks, I |
| author_sort | Carral, D |
| collection | OXFORD |
| description | We identify a class of Horn ontologies for which standard reasoning tasks such as instance checking and classification are tractable. The class is general enough to include the OWL 2 EL, QL, and RL profiles. Verifying whether a Horn ontology belongs to the class can be done in polynomial time. We show empirically that the class includes many real-world ontologies that are not included in any OWL 2 profile, and thus that polynomial time reasoning is possible for these ontologies. |
| first_indexed | 2024-03-06T19:44:58Z |
| format | Conference item |
| id | oxford-uuid:21f8c6a3-c6ce-4002-ae05-f8414ff07f7e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-03-11T16:57:48Z |
| publishDate | 2014 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | oxford-uuid:21f8c6a3-c6ce-4002-ae05-f8414ff07f7e2025-03-05T10:20:01ZPushing the boundaries of tractable ontology reasoningConference itemhttp://purl.org/coar/resource_type/c_5794uuid:21f8c6a3-c6ce-4002-ae05-f8414ff07f7eComputer science (mathematics)Applications and algorithmsTheory and automated verificationEnglishOxford University Research Archive - ValetSpringer International Publishing2014Carral, DFeier, CGrau, BCHitzler, PHorrocks, IWe identify a class of Horn ontologies for which standard reasoning tasks such as instance checking and classification are tractable. The class is general enough to include the OWL 2 EL, QL, and RL profiles. Verifying whether a Horn ontology belongs to the class can be done in polynomial time. We show empirically that the class includes many real-world ontologies that are not included in any OWL 2 profile, and thus that polynomial time reasoning is possible for these ontologies. |
| spellingShingle | Computer science (mathematics) Applications and algorithms Theory and automated verification Carral, D Feier, C Grau, BC Hitzler, P Horrocks, I Pushing the boundaries of tractable ontology reasoning |
| title | Pushing the boundaries of tractable ontology reasoning |
| title_full | Pushing the boundaries of tractable ontology reasoning |
| title_fullStr | Pushing the boundaries of tractable ontology reasoning |
| title_full_unstemmed | Pushing the boundaries of tractable ontology reasoning |
| title_short | Pushing the boundaries of tractable ontology reasoning |
| title_sort | pushing the boundaries of tractable ontology reasoning |
| topic | Computer science (mathematics) Applications and algorithms Theory and automated verification |
| work_keys_str_mv | AT carrald pushingtheboundariesoftractableontologyreasoning AT feierc pushingtheboundariesoftractableontologyreasoning AT graubc pushingtheboundariesoftractableontologyreasoning AT hitzlerp pushingtheboundariesoftractableontologyreasoning AT horrocksi pushingtheboundariesoftractableontologyreasoning |