2026-07-25T19:05:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7678 2024-03-06T10:40:45Z ddc:004 open_access

Fast(er) Reasoning in Interval Temporal Logic Bresolin, Davide Muñoz-Velasco, Emilio Sciavicco, Guido Temporal Logic Horn Fragments Satisfiability Complexity Clausal forms of logics are of great relevance in Artificial Intelligence, because they couple a high expressivity with a low complexity of reasoning problems. They have been studied for a wide range of classical, modal and temporal logics to obtain tractable fragments of intractable formalisms. In this paper we show that such restrictions can be exploited to lower the complexity of interval temporal logics as well. In particular, we show that for the Horn fragment of the interval logic AAbar (that is, the logic with the modal operators for Allen’s relations meets and met by) without diamonds the complexity lowers from NEXPTIME-complete to P-complete. We prove also that the tractability of the Horn fragments of interval temporal logics is lost as soon as other interval temporal operators are added to AAbar, in most of the cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bresolin and Emilio Muñoz-Velasco and Guido Sciavicco 2017 Is Part Of LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2017.17 urn:nbn:de:0030-drops-76782 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.17 eng https://creativecommons.org/licenses/by/3.0/legalcode