License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.17
URN: urn:nbn:de:0030-drops-76782
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7678/
Go to the corresponding LIPIcs Volume Portal

Bresolin, Davide ; Muñoz-Velasco, Emilio ; Sciavicco, Guido

Fast(er) Reasoning in Interval Temporal Logic

pdf-format:
LIPIcs-CSL-2017-17.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bresolin_et_al:LIPIcs:2017:7678,
  author =	{Davide Bresolin and Emilio Mu{\~n}oz-Velasco and Guido Sciavicco},
  title =	{{Fast(er) Reasoning in Interval Temporal Logic}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7678},
  URN =		{urn:nbn:de:0030-drops-76782},
  doi =		{10.4230/LIPIcs.CSL.2017.17},
  annote =	{Keywords: Temporal Logic, Horn Fragments, Satisfiability, Complexity}
}

Keywords: Temporal Logic, Horn Fragments, Satisfiability, Complexity
Collection: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 16.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI