Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions

Davide Bresolin; Valentin Goranko; Angelo Montanari; Guido Sciavicco

doi:10.1016/j.apal.2009.07.003

Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions

Davide Bresolin, Valentin Goranko, Angelo Montanari, Guido Sciavicco

Research output: Contribution to journal › Journal article › Research › peer-review

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.

Original language	English
Journal	Annals of Pure and Applied Logic
Volume	161
Issue number	3
Pages (from-to)	289-304
ISSN	0168-0072
DOIs	https://doi.org/10.1016/j.apal.2009.07.003
Publication status	Published - 2009

Keywords

Two-variable fragment
Neighborhood interval logics
Undecidability
Expressiveness
Decidability

Access to Document

10.1016/j.apal.2009.07.003

OpenUrl availability

Full text

Cite this

@article{c061fb416aba4154ad6cd2aa30c22411,

title = "Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions",

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{\textquoteright}s interval logic HS.",

keywords = "Two-variable fragment, Neighborhood interval logics, Undecidability, Expressiveness, Decidability",

author = "Davide Bresolin and Valentin Goranko and Angelo Montanari and Guido Sciavicco",

year = "2009",

doi = "10.1016/j.apal.2009.07.003",

language = "English",

volume = "161",

pages = "289--304",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions

AU - Bresolin, Davide

AU - Goranko, Valentin

AU - Montanari, Angelo

AU - Sciavicco, Guido

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Two-variable fragment

KW - Neighborhood interval logics

KW - Undecidability

KW - Expressiveness

KW - Decidability

U2 - 10.1016/j.apal.2009.07.003

DO - 10.1016/j.apal.2009.07.003

M3 - Journal article

SN - 0168-0072

VL - 161

SP - 289

EP - 304

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 3

ER -

Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this