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 AA (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 AA, in most of the cases.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | Fast(er) Reasoning in Interval Temporal Logic | |
Autori: | ||
Data di pubblicazione: | 2017 | |
Serie: | ||
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 AA (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 AA, in most of the cases. | |
Handle: | http://hdl.handle.net/11392/2373984 | |
Appare nelle tipologie: | 04.2 Contributi in atti di convegno (in Volume) |