The classication of the fragments of Halpern and Shoham's logic with respect to decidability/undecidability of the satisfiability problem is now very close to the end. We settle one of the few remaining questions concerning the fragment AAbarBBbar, which comprises Allen's interval relations "meets" and "begins" and their symmetric versions. We already proved that AAbarBBbar is decidable over the class of all finite linear orders and undecidable over ordered domains isomorphic to N. In this paper, we first show that AAbarBBbar is undecidable over R and over the class of all Dedekind-complete linear orders. We then prove that the logic is decidable over Q and over the class of all linear orders.

Decidability of the interval temporal logic AA*BB* over the rationals

MONTANARI, Angelo
;
Puppis G
;
2014-01-01

Abstract

The classication of the fragments of Halpern and Shoham's logic with respect to decidability/undecidability of the satisfiability problem is now very close to the end. We settle one of the few remaining questions concerning the fragment AAbarBBbar, which comprises Allen's interval relations "meets" and "begins" and their symmetric versions. We already proved that AAbarBBbar is decidable over the class of all finite linear orders and undecidable over ordered domains isomorphic to N. In this paper, we first show that AAbarBBbar is undecidable over R and over the class of all Dedekind-complete linear orders. We then prove that the logic is decidable over Q and over the class of all linear orders.
2014
9783662445211
File in questo prodotto:
File Dimensione Formato  
mfcs2014cr.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: Non pubblico
Dimensione 246.08 kB
Formato Adobe PDF
246.08 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/1036951
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact