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π + , 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π + is expressively complete with respect to such a fragment. We conclude the paper by comparing PNLπ + expressiveness with that of other interval-based temporal logics.
On Decidability and Expressiveness of Propositional Interval Neighborhood Logics / Davide Bresolin; Valentin Goranko; Angelo Montanari; Guido Sciavicco. - STAMPA. - 4514:(2007), pp. 84-99. (Intervento presentato al convegno International Symposium, LFCS 2007 tenutosi a New York, NY, USA nel June 4-7, 2007) [10.1007/978-3-540-72734-7_7].
On Decidability and Expressiveness of Propositional Interval Neighborhood Logics
BRESOLIN, DAVIDE;
2007
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π + , 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π + is expressively complete with respect to such a fragment. We conclude the paper by comparing PNLπ + expressiveness with that of other interval-based temporal logics.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
