{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T00:36:01Z","timestamp":1768437361199,"version":"3.49.0"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T00:00:00Z","timestamp":1690934400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce negation under the stable model semantics in DatalogMTL \u2013 a temporal extension of Datalog with metric temporal operators. As a result, we obtain a rule language which combines the power of answer set programming with the temporal dimension provided by metric operators. We show that, in this setting, reasoning becomes undecidable over the rational timeline, and decidable in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S1471068423000315_inline1.png\"\/><jats:tex-math>\n${{\\rm E}{\\small\\rm XP}{\\rm S}{\\small\\rm PACE}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in data complexity over the integer timeline. We also show that, if we restrict our attention to forward-propagating programs, reasoning over the integer timeline becomes <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S1471068423000315_inline2.png\"\/><jats:tex-math>\n${{\\rm PS}{\\small\\rm PACE}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-complete in data complexity, and hence, no harder than over positive programs; however, reasoning over the rational timeline in this fragment remains undecidable.<\/jats:p>","DOI":"10.1017\/s1471068423000315","type":"journal-article","created":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T05:52:50Z","timestamp":1690955570000},"page":"22-56","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["The Stable Model Semantics of Datalog with Metric Temporal Operators"],"prefix":"10.1017","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2922-0472","authenticated-orcid":false,"given":"PRZEMYS\u0141AW A.","family":"WA\u0141\u0118GA","sequence":"first","affiliation":[]},{"given":"DAVID J.","family":"TENA CUCALA","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2909-5923","authenticated-orcid":false,"given":"BERNARDO","family":"CUENCA GRAU","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8886-6129","authenticated-orcid":false,"given":"EGOR V.","family":"KOSTYLEV","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,8,2]]},"reference":[{"key":"S1471068423000315_ref21","doi-asserted-by":"crossref","unstructured":"Faber, W. , Leone, N. and Pfeifer, G. 2004. Recursive aggregates in disjunctive logic programs: Semantics and complexity. In Proceedings of the 9th European Conference on Logics in Artificial Intelligence, 200\u2013212.","DOI":"10.1007\/978-3-540-30227-8_19"},{"key":"S1471068423000315_ref23","unstructured":"Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming, Proceedings of the Fifth International Conference and Symposium, 1070\u20131080."},{"key":"S1471068423000315_ref20","doi-asserted-by":"crossref","unstructured":"Eiter, T. , Ianni, G. and Krennwallner, T. 2009. Answer set programming: A primer. In Reasoning Web International Summer School. Springer, 40\u2013110.","DOI":"10.1007\/978-3-642-03754-2_2"},{"key":"S1471068423000315_ref40","doi-asserted-by":"crossref","unstructured":"Zaniolo, C. 2012. Logical foundations of continuous query languages for data streams. In Proceedings of the 2nd International Workshop on Datalog in Academia and Industry, 177\u2013189.","DOI":"10.1007\/978-3-642-32925-8_18"},{"key":"S1471068423000315_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01995674"},{"key":"S1471068423000315_ref10","doi-asserted-by":"crossref","unstructured":"Brandt, S. , Kontchakov, R. , Ryzhikov, V. , Xiao, G. and Zakharyaschev, M. 2017. Ontology-based data access with a Horn fragment of metric temporal logic. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, 1070\u20131076.","DOI":"10.1609\/aaai.v31i1.10696"},{"key":"S1471068423000315_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(89)80070-7"},{"key":"S1471068423000315_ref16","doi-asserted-by":"crossref","unstructured":"Cabalar, P. and Vega, G. P. 2007. Temporal equilibrium logic: A first approach. In Proceedings of the 11th International Conference on Computer Aided Systems Theory, 241\u2013248.","DOI":"10.1007\/978-3-540-75867-9_31"},{"key":"S1471068423000315_ref28","doi-asserted-by":"crossref","unstructured":"Pnueli, A. 1977. The temporal logic of programs. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 46\u201357.","DOI":"10.1109\/SFCS.1977.32"},{"key":"S1471068423000315_ref36","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0119ga, P. A. , Cuenca Grau, B. , Kaminski, M. and Kostylev, E. V. 2019. DatalogMTL: Computational complexity and expressive power. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 1886\u20131892.","DOI":"10.24963\/ijcai.2019\/261"},{"key":"S1471068423000315_ref9","doi-asserted-by":"crossref","unstructured":"Brandt, S. , Kalayc, E. G. , Ryzhikov, V. , Xiao, G. and Zakharyaschev, M. 2018. Querying log data with metric temporal logic. Journal of Artificial Intelligence Resesearch 62, 829 \u2013 877.","DOI":"10.1613\/jair.1.11229"},{"key":"S1471068423000315_ref34","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0119ga, P. , Cuenca Grau, B. and Kaminski, M. 2019. Reasoning over streaming data in metric temporal Datalog. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 1941\u20131948.","DOI":"10.1609\/aaai.v33i01.33013092"},{"key":"S1471068423000315_ref27","doi-asserted-by":"crossref","unstructured":"Pearce, D. 1996. A new logical characterisation of stable models and answer sets. In Proceedings of the International Workshop on Non-monotonic Extensions of Logic Programming, 57\u201370.","DOI":"10.1007\/BFb0023801"},{"key":"S1471068423000315_ref29","unstructured":"Ronca, A. , Kaminski, M. , Cuenca Grau, B. and Horrocks, I. 2018. The window validity problem in rule-based stream reasoning. In Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, 571\u2013580."},{"key":"S1471068423000315_ref37","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0119ga, P. A. , Cuenca Grau, B. , Kaminski, M. and Kostylev, E. V. 2020b. Tractable fragments of Datalog with metric temporal operators. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, 1919\u20131925.","DOI":"10.24963\/ijcai.2020\/266"},{"key":"S1471068423000315_ref32","doi-asserted-by":"crossref","unstructured":"Tena Cucala, D. , Wa\u0142\u0119ga, P. A. , Cuenca Grau, B. and Kostylev, E. V. 2021. Stratified negation in Datalog with metric temporal operators. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, 6488\u20136495.","DOI":"10.1609\/aaai.v35i7.16804"},{"key":"S1471068423000315_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-017-0295-4"},{"key":"S1471068423000315_ref4","author":"Baier","year":"2008"},{"key":"S1471068423000315_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000297"},{"key":"S1471068423000315_ref2","volume-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"key":"S1471068423000315_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40564-8_34"},{"key":"S1471068423000315_ref31","doi-asserted-by":"crossref","unstructured":"Ryzhikov, V. , Wa\u0142\u0119ga, P. A. and Zakharyaschev, M. 2019. Data complexity and rewritability of ontology-mediated queries in metric temporal logic under the event-based semantics. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 1851\u20131857.","DOI":"10.24963\/ijcai.2019\/256"},{"key":"S1471068423000315_ref5","doi-asserted-by":"crossref","unstructured":"Baldor, K. and Niu, J. 2012. Monitoring dense-time, continuous-semantics, metric temporal logic. In Runtime Verification, Third International Conference, Revised Selected Papers, vol. 7687, 245\u2013259.","DOI":"10.1007\/978-3-642-35632-2_24"},{"key":"S1471068423000315_ref17","doi-asserted-by":"crossref","unstructured":"Chomicki, J. and Imieli\u0144ski, T. 1988. Temporal deductive databases and infinite objects. In Proceedings of thes 7th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 61\u201373.","DOI":"10.1145\/308386.308416"},{"key":"S1471068423000315_ref24","unstructured":"Heyting, A. 1930. Die formalen regeln der intuitionistischen logik. In Sitzungsberichte der Preussischen Akademie der Wissenschaften, physikalisch-mathematische klass, 42\u201356."},{"key":"S1471068423000315_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068420000307"},{"key":"S1471068423000315_ref35","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0119ga, P. , Cuenca Grau, B. , Kaminski, M. and Kostylev, E. V. 2020a. DatalogMTL over the integer timeline. In Proceedings of the 17th International Conference on the Principles of Knowledge Representation and Reasoning, 526\u2013541.","DOI":"10.24963\/kr.2020\/79"},{"key":"S1471068423000315_ref39","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0119ga, P. A. , Zawidzki, M. and Cuenca Grau, B. 2021. Finitely materialisable Datalog programs with metric temporal operators. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, 619\u2013628.","DOI":"10.24963\/kr.2021\/59"},{"key":"S1471068423000315_ref3","doi-asserted-by":"publisher","DOI":"10.1080\/11663081.2013.798985"},{"key":"S1471068423000315_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2018.04.003"},{"key":"S1471068423000315_ref19","doi-asserted-by":"crossref","unstructured":"Do, T. M. , Loke, S. W. and Liu, F. 2011. Answer set programming for stream reasoning. In Proceedings of the 24th Canadian Conference on Artificial Intelligence, vol. 6657. Springer, 104\u2013109.","DOI":"10.1007\/978-3-642-21043-3_13"},{"key":"S1471068423000315_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45241-9_12"},{"key":"S1471068423000315_ref33","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i5.20535"},{"key":"S1471068423000315_ref30","doi-asserted-by":"crossref","unstructured":"Ronca, A. , Kaminski, M. , Cuenca Grau, B. , Motik, B. and Horrocks, I. 2018. Stream reasoning in temporal Datalog. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, 1941\u20131948.","DOI":"10.1609\/aaai.v32i1.11537"},{"key":"S1471068423000315_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00139-4"},{"key":"S1471068423000315_ref38","doi-asserted-by":"crossref","unstructured":"Wa\u0142\u0119ga, P. A. , Tena Cucala, D. J. , Kostylev, E. V. and Cuenca Grau, B. 2021. DatalogMTL with negation under stable models semantics. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, 609\u2013618.","DOI":"10.24963\/kr.2021\/58"},{"key":"S1471068423000315_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-007-9082-1"},{"key":"S1471068423000315_ref18","doi-asserted-by":"crossref","unstructured":"Chomicki, J. and Imieli\u0144ski, T. 1989. Relational specifications of infinite query answers. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, 174\u2013183.","DOI":"10.1145\/66926.66942"},{"key":"S1471068423000315_ref13","doi-asserted-by":"crossref","unstructured":"Cabalar, P. and Demri, S. 2011. Automata-based computation of temporal equilibrium models. In International Symposium on Logic-Based Program Synthesis and Transformation, Revised Selected Papers, 57\u201372.","DOI":"10.1007\/978-3-642-32211-2_5"},{"key":"S1471068423000315_ref8","doi-asserted-by":"crossref","unstructured":"Bozzelli, L. and Pearce, D. 2015. On the complexity of temporal equilibrium logic. In Proceedings of the 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, 645\u2013656.","DOI":"10.1109\/LICS.2015.65"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068423000315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,29]],"date-time":"2023-12-29T11:09:38Z","timestamp":1703848178000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068423000315\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,2]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["S1471068423000315"],"URL":"https:\/\/doi.org\/10.1017\/s1471068423000315","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,2]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}