Stratified negation in datalog with metric temporal operators
We extend DatalogMTL—Datalog with operators from metric temporal logic—by adding stratified negation as failure. The new language provides additional expressive power for representing and reasoning about temporal data and knowledge in a wide range of applications. We consider models over the rationa...
| Główni autorzy: | , , , |
|---|---|
| Format: | Conference item |
| Język: | English |
| Wydane: |
AAAI Press
2021
|
| _version_ | 1826278541080133632 |
|---|---|
| author | Tena Cucala, D Walega, P Cuenca Grau, B Kostylev, E |
| author_facet | Tena Cucala, D Walega, P Cuenca Grau, B Kostylev, E |
| author_sort | Tena Cucala, D |
| collection | OXFORD |
| description | We extend DatalogMTL—Datalog with operators from metric temporal logic—by adding stratified negation as failure. The new language provides additional expressive power for representing and reasoning about temporal data and knowledge in a wide range of applications. We consider models over the rational timeline, study their properties, and establish the computational complexity of reasoning. We show that, as in negation-free DatalogMTL, fact entailment in our language is PSPACE-complete in data and EXPSPACE-complete in combined complexity. Thus, the extension with stratified negation does not lead to higher complexity. |
| first_indexed | 2024-03-06T23:45:27Z |
| format | Conference item |
| id | oxford-uuid:70bfb39f-9f72-41c2-9da4-6f78a56db65b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:45:27Z |
| publishDate | 2021 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | oxford-uuid:70bfb39f-9f72-41c2-9da4-6f78a56db65b2022-03-26T19:39:11ZStratified negation in datalog with metric temporal operatorsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:70bfb39f-9f72-41c2-9da4-6f78a56db65bEnglishSymplectic ElementsAAAI Press2021Tena Cucala, DWalega, PCuenca Grau, BKostylev, EWe extend DatalogMTL—Datalog with operators from metric temporal logic—by adding stratified negation as failure. The new language provides additional expressive power for representing and reasoning about temporal data and knowledge in a wide range of applications. We consider models over the rational timeline, study their properties, and establish the computational complexity of reasoning. We show that, as in negation-free DatalogMTL, fact entailment in our language is PSPACE-complete in data and EXPSPACE-complete in combined complexity. Thus, the extension with stratified negation does not lead to higher complexity. |
| spellingShingle | Tena Cucala, D Walega, P Cuenca Grau, B Kostylev, E Stratified negation in datalog with metric temporal operators |
| title | Stratified negation in datalog with metric temporal operators |
| title_full | Stratified negation in datalog with metric temporal operators |
| title_fullStr | Stratified negation in datalog with metric temporal operators |
| title_full_unstemmed | Stratified negation in datalog with metric temporal operators |
| title_short | Stratified negation in datalog with metric temporal operators |
| title_sort | stratified negation in datalog with metric temporal operators |
| work_keys_str_mv | AT tenacucalad stratifiednegationindatalogwithmetrictemporaloperators AT walegap stratifiednegationindatalogwithmetrictemporaloperators AT cuencagraub stratifiednegationindatalogwithmetrictemporaloperators AT kostyleve stratifiednegationindatalogwithmetrictemporaloperators |