Query answering with transitive and linear-ordered data
We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure o...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
International Joint Conferences on Artificial Intelligence
2016
|
| _version_ | 1797053066357243904 |
|---|---|
| author | Vanden Boom, M Benedikt, M Amarilli, A Bourhis, P |
| author_facet | Vanden Boom, M Benedikt, M Amarilli, A Bourhis, P |
| author_sort | Vanden Boom, M |
| collection | OXFORD |
| description | We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability. |
| first_indexed | 2024-03-06T18:38:49Z |
| format | Conference item |
| id | oxford-uuid:0c326fa9-3a28-44ab-a589-69d36caf9256 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:38:49Z |
| publishDate | 2016 |
| publisher | International Joint Conferences on Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:0c326fa9-3a28-44ab-a589-69d36caf92562022-03-26T09:33:37ZQuery answering with transitive and linear-ordered dataConference itemhttp://purl.org/coar/resource_type/c_5794uuid:0c326fa9-3a28-44ab-a589-69d36caf9256Symplectic Elements at OxfordInternational Joint Conferences on Artificial Intelligence2016Vanden Boom, MBenedikt, MAmarilli, ABourhis, PWe consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability. |
| spellingShingle | Vanden Boom, M Benedikt, M Amarilli, A Bourhis, P Query answering with transitive and linear-ordered data |
| title | Query answering with transitive and linear-ordered data |
| title_full | Query answering with transitive and linear-ordered data |
| title_fullStr | Query answering with transitive and linear-ordered data |
| title_full_unstemmed | Query answering with transitive and linear-ordered data |
| title_short | Query answering with transitive and linear-ordered data |
| title_sort | query answering with transitive and linear ordered data |
| work_keys_str_mv | AT vandenboomm queryansweringwithtransitiveandlinearordereddata AT benediktm queryansweringwithtransitiveandlinearordereddata AT amarillia queryansweringwithtransitiveandlinearordereddata AT bourhisp queryansweringwithtransitiveandlinearordereddata |