Tractable Extensions of the Description Logic EL with Numerical Datatypes
We consider extensions of the lightweight description logic (DL) ε ℓ with numerical datatypes such as naturals, integers, rationals and reals equipped with relations such as equality and inequalities. It is well-known that the main reasoning problems for such DLs are decidable in polynomial time pro...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2011
|
| _version_ | 1826285356364857344 |
|---|---|
| author | Magka, D Kazakov, Y Horrocks, I |
| author_facet | Magka, D Kazakov, Y Horrocks, I |
| author_sort | Magka, D |
| collection | OXFORD |
| description | We consider extensions of the lightweight description logic (DL) ε ℓ with numerical datatypes such as naturals, integers, rationals and reals equipped with relations such as equality and inequalities. It is well-known that the main reasoning problems for such DLs are decidable in polynomial time provided that the datatypes enjoy the so-called convexity property. Unfortunately many combinations of the numerical relations violate convexity, which makes the usage of these datatypes rather limited in practice. In this paper, we make a more fine-grained complexity analysis of these DLs by considering restrictions not only on the kinds of relations that can be used in ontologies but also on their occurrences, such as allowing certain relations to appear only on the left-hand side of the axioms. To this end, we introduce a notion of safety for a numerical datatype with restrictions (NDR) which guarantees tractability, extend the ε ℓ reasoning algorithm to these cases, and provide a complete classification of safe NDRs for natural numbers, integers, rationals and reals. © 2011 Springer Science+Business Media B.V. |
| first_indexed | 2024-03-07T01:27:36Z |
| format | Journal article |
| id | oxford-uuid:92805a90-6840-4632-af38-62a63b78db56 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:27:36Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:92805a90-6840-4632-af38-62a63b78db562022-03-26T23:25:57ZTractable Extensions of the Description Logic EL with Numerical DatatypesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:92805a90-6840-4632-af38-62a63b78db56EnglishSymplectic Elements at Oxford2011Magka, DKazakov, YHorrocks, IWe consider extensions of the lightweight description logic (DL) ε ℓ with numerical datatypes such as naturals, integers, rationals and reals equipped with relations such as equality and inequalities. It is well-known that the main reasoning problems for such DLs are decidable in polynomial time provided that the datatypes enjoy the so-called convexity property. Unfortunately many combinations of the numerical relations violate convexity, which makes the usage of these datatypes rather limited in practice. In this paper, we make a more fine-grained complexity analysis of these DLs by considering restrictions not only on the kinds of relations that can be used in ontologies but also on their occurrences, such as allowing certain relations to appear only on the left-hand side of the axioms. To this end, we introduce a notion of safety for a numerical datatype with restrictions (NDR) which guarantees tractability, extend the ε ℓ reasoning algorithm to these cases, and provide a complete classification of safe NDRs for natural numbers, integers, rationals and reals. © 2011 Springer Science+Business Media B.V. |
| spellingShingle | Magka, D Kazakov, Y Horrocks, I Tractable Extensions of the Description Logic EL with Numerical Datatypes |
| title | Tractable Extensions of the Description Logic EL with Numerical Datatypes |
| title_full | Tractable Extensions of the Description Logic EL with Numerical Datatypes |
| title_fullStr | Tractable Extensions of the Description Logic EL with Numerical Datatypes |
| title_full_unstemmed | Tractable Extensions of the Description Logic EL with Numerical Datatypes |
| title_short | Tractable Extensions of the Description Logic EL with Numerical Datatypes |
| title_sort | tractable extensions of the description logic el with numerical datatypes |
| work_keys_str_mv | AT magkad tractableextensionsofthedescriptionlogicelwithnumericaldatatypes AT kazakovy tractableextensionsofthedescriptionlogicelwithnumericaldatatypes AT horrocksi tractableextensionsofthedescriptionlogicelwithnumericaldatatypes |