In this paper, we investigate the expressiveness of the variety of propositional interval neighborhood logics (PNL), we establish their decidability on linearly ordered domains and some important subclasses, and we prove the undecidability of a number of extensions of PNL with additional modalities over interval relations. All together, we show that PNL form a quite expressive and nearly maximal decidable fragment of Halpern–Shoham's interval logic HS.
Propositional Interval Neighborhood Logics: Expressiveness, Decidability, and Undecidable Extensions
MONTANARI, Angelo;
2009-01-01
Abstract
In this paper, we investigate the expressiveness of the variety of propositional interval neighborhood logics (PNL), we establish their decidability on linearly ordered domains and some important subclasses, and we prove the undecidability of a number of extensions of PNL with additional modalities over interval relations. All together, we show that PNL form a quite expressive and nearly maximal decidable fragment of Halpern–Shoham's interval logic HS.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
APAL2009.pdf
non disponibili
Tipologia:
Altro materiale allegato
Licenza:
Non pubblico
Dimensione
989.79 kB
Formato
Adobe PDF
|
989.79 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.
