Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions |
| |
| Authors: | Davide Bresolin Valentin Goranko Angelo Montanari Guido Sciavicco |
| |
| Institution: | aDepartment of Computer Science, University of Verona, Italy;bDepartment of Informatics and Mathematical Modelling, Technical University of Denmark, Denmark;cDepartment of Mathematics and Computer Science, University of Udine, Italy;dDepartment of Information Engineering and Communications, University of Murcia, Spain |
| |
| 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. |
| |
| Keywords: | Neighborhood interval logics Expressiveness Two-variable fragment Decidability Undecidability |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
