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.

D. Bresolin, V. Goranko, A. Montanari, G. Sciavicco (2009). Propositional Interval Neighborhood Logics: Expressiveness, Decidability, and Undecidable Extensions. ANNALS OF PURE AND APPLIED LOGIC, 161, 289-304 [10.1016/j.apal.2009.07.003].

Propositional Interval Neighborhood Logics: Expressiveness, Decidability, and Undecidable Extensions

BRESOLIN, DAVIDE;
2009

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.
2009
D. Bresolin, V. Goranko, A. Montanari, G. Sciavicco (2009). Propositional Interval Neighborhood Logics: Expressiveness, Decidability, and Undecidable Extensions. ANNALS OF PURE AND APPLIED LOGIC, 161, 289-304 [10.1016/j.apal.2009.07.003].
D. Bresolin; V. Goranko; A. Montanari; G. Sciavicco
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/371937
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 71
  • ???jsp.display-item.citation.isi??? 52
social impact