Interval-based temporal logics are an important research area in computer science and artificial intelligence. In this paper we investigate decidability and expressiveness issues for Propositional Neighborhood Logics (PNLs). We begin by comparing the expressiveness of the different PNLs. Then, we focus on the most expressive one, namely, PNL^PI_+, and we show that it is decidable over various classes of linear orders by reducing its satisfiability problem to that of the two-variable fragment of first-order logic with binary relations over linearly ordered domains, due to Otto. Next, we prove that PNL^Pi_+ is expressively complete with respect to such a fragment. We conclude the paper by comparing PNL^Pi_+ expressiveness with that of other interval-based temporal logics.
On Decidability and Expressiveness of Propositional Interval Neighborhood Logics
BRESOLIN, Davide;MONTANARI, Angelo;
2007-01-01
Abstract
Interval-based temporal logics are an important research area in computer science and artificial intelligence. In this paper we investigate decidability and expressiveness issues for Propositional Neighborhood Logics (PNLs). We begin by comparing the expressiveness of the different PNLs. Then, we focus on the most expressive one, namely, PNL^PI_+, and we show that it is decidable over various classes of linear orders by reducing its satisfiability problem to that of the two-variable fragment of first-order logic with binary relations over linearly ordered domains, due to Otto. Next, we prove that PNL^Pi_+ is expressively complete with respect to such a fragment. We conclude the paper by comparing PNL^Pi_+ expressiveness with that of other interval-based temporal logics.File | Dimensione | Formato | |
---|---|---|---|
PNLexpressiveness061208.pdf
non disponibili
Tipologia:
Documento in Pre-print
Licenza:
Non pubblico
Dimensione
220.25 kB
Formato
Adobe PDF
|
220.25 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.