The introduction of Halpern and Shoham's modal logic of intervals (later on called HS) dates back to 1986. Despite its natural semantics, this logic is undecidable over all interesting classes of temporal structures. This discouraged research in this area until recently, when a number of non-trivial decidable fragments have been found. This paper is a contribution toward the complete classification of HS fragments. Different combinations of Allen's interval relations begins (B), meets (A), and later (L), and their inverses Abar, Bbar, and Lbar, have been considered in the literature. We know from previous work that the combination AAbarBBbar is decidable over finite linear orders and undecidable everywhere else. We extend these results by showing that ALbarBBbar is decidable over the class of all (resp., dense, discrete) linear orders, and that it is maximal with respect to decidability over these classes: adding any other interval modality immediately leads to undecidability.

What's decidable about Halpern and Shoham's interval logic? The maximal fragment ABBbarLbar

MONTANARI, Angelo;
2011-01-01

Abstract

The introduction of Halpern and Shoham's modal logic of intervals (later on called HS) dates back to 1986. Despite its natural semantics, this logic is undecidable over all interesting classes of temporal structures. This discouraged research in this area until recently, when a number of non-trivial decidable fragments have been found. This paper is a contribution toward the complete classification of HS fragments. Different combinations of Allen's interval relations begins (B), meets (A), and later (L), and their inverses Abar, Bbar, and Lbar, have been considered in the literature. We know from previous work that the combination AAbarBBbar is decidable over finite linear orders and undecidable everywhere else. We extend these results by showing that ALbarBBbar is decidable over the class of all (resp., dense, discrete) linear orders, and that it is maximal with respect to decidability over these classes: adding any other interval modality immediately leads to undecidability.
2011
9780769544120
File in questo prodotto:
File Dimensione Formato  
lics2011.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Non pubblico
Dimensione 260.17 kB
Formato Adobe PDF
260.17 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11390/867902
 Attenzione

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

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