{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:32:15Z","timestamp":1723015935203},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"We study the complexity and expressive power of DatalogMTL - a knowledge representation language that extends Datalog with operators from metric temporal logic (MTL) and which has found applications in ontology-based data access and stream reasoning. We establish tight PSpace data complexity bounds and also show that DatalogMTL extended with negation on input predicates can express all queries in PSpace; this implies that MTL operators add significant expressive power to Datalog. Furthermore, we provide tight combined complexity bounds for the forward-propagating fragment of DatalogMTL, which was proposed in the context of stream reasoning, and show that it is possible to express all PSpace queries in the fragment extended with the falsum predicate.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/261","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T07:46:05Z","timestamp":1564299965000},"page":"1886-1892","source":"Crossref","is-referenced-by-count":9,"title":["DatalogMTL: Computational Complexity and Expressive Power"],"prefix":"10.24963","author":[{"given":"Przemys\u0142aw A.","family":"Wa\u0142\u0119ga","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, UK"},{"name":"Institute of Philosophy, University of Warsaw, Poland"}]},{"given":"Bernardo","family":"Cuenca Grau","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, UK"}]},{"given":"Mark","family":"Kaminski","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, UK"}]},{"given":"Egor V.","family":"Kostylev","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, UK"}]}],"member":"10584","event":{"number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2019","name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","start":{"date-parts":[[2019,8,10]]},"theme":"Artificial Intelligence","location":"Macao, China","end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T07:47:57Z","timestamp":1564300077000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/261"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/261","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}