Unlike the Moon, the dark side of interval temporal logics is the one we usually see: their ubiquitous undecidability. Identifying minimal undecidable interval logics is thus a natural and important issue in that research area. In this paper, we identify several new minimal undecidable logics amongst the fragments of Halpern and Shoham’s logic HS, including the logic of the overlaps relation, over the classes of all finite linear orders and all linear orders, as well as the logic of the meets and subinterval relations, over the classes of all and dense linear orders. Together with previous undecidability results, this work contributes to bringing the identification of the dark side of interval temporal logics very close to the definitive picture.

The dark side of interval temporal logic: marking the undecidability border / Davide Bresolin; Dario Della Monica; Valentin Goranko; Angelo Montanari; Guido Sciavicco. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - STAMPA. - 71:1-3(2014), pp. 41-83. [10.1007/s10472-013-9376-4]

The dark side of interval temporal logic: marking the undecidability border

BRESOLIN, DAVIDE;
2014

Abstract

Unlike the Moon, the dark side of interval temporal logics is the one we usually see: their ubiquitous undecidability. Identifying minimal undecidable interval logics is thus a natural and important issue in that research area. In this paper, we identify several new minimal undecidable logics amongst the fragments of Halpern and Shoham’s logic HS, including the logic of the overlaps relation, over the classes of all finite linear orders and all linear orders, as well as the logic of the meets and subinterval relations, over the classes of all and dense linear orders. Together with previous undecidability results, this work contributes to bringing the identification of the dark side of interval temporal logics very close to the definitive picture.
2014
The dark side of interval temporal logic: marking the undecidability border / Davide Bresolin; Dario Della Monica; Valentin Goranko; Angelo Montanari; Guido Sciavicco. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - STAMPA. - 71:1-3(2014), pp. 41-83. [10.1007/s10472-013-9376-4]
Davide Bresolin; Dario Della Monica; Valentin Goranko; Angelo Montanari; Guido Sciavicco
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/371946
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? 27
social impact