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 the research agenda in the area. The decidability status of a logic often depends on the class of models (in our case, the class of interval structures) in which it is interpreted. In this paper, we have identified several new minimal undecidable logics amongst the fragments of Halpern-Shoham logic HS, including the logic of the overlaps relation, over the classes of all and finite linear orders, as well as the logic of the meet and subinterval relations, over the class of dense linear orders. Together with previous undecidability results, this work contributes to delineate the border of the dark side of interval temporal logics quite sharply.

The Dark Side of Interval Temporal Logics: Sharpening the Undecidability Border

SCIAVICCO, Guido
2011

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 the research agenda in the area. The decidability status of a logic often depends on the class of models (in our case, the class of interval structures) in which it is interpreted. In this paper, we have identified several new minimal undecidable logics amongst the fragments of Halpern-Shoham logic HS, including the logic of the overlaps relation, over the classes of all and finite linear orders, as well as the logic of the meet and subinterval relations, over the class of dense linear orders. Together with previous undecidability results, this work contributes to delineate the border of the dark side of interval temporal logics quite sharply.
2011
978-1-4577-1242-5
978-0-7695-4508-0
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in SFERA 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/11392/2326778
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? ND
social impact