Metric propositional neighborhood logic with an equivalence relation

详细信息    查看全文

• 作者：Angelo Montanari ; Marco Pazzaglia ; Pietro Sala
• 刊名：Acta Informatica
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：53
• 期：6-8
• 页码：621-648
• 全文大小：654 KB
• 刊物类别：Computer Science
• 刊物主题：Logics and Meanings of Programs
  Computer Systems Organization and Communication Networks
  Software Engineering, Programming and Operating Systems
  Data Structures, Cryptology and Information Theory
  Theory of Computation
  Information Systems and Communication Service
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1432-0525
• 卷排序：53

文摘

The propositional interval logic of temporal neighborhood (PNL for short) features two modalities that make it possible to access intervals adjacent to the right (modality \(\langle A \rangle \)) and to the left (modality \(\langle \overline{A}\rangle \)) of the current interval. PNL stands at a central position in the realm of interval temporal logics, as it is expressive enough to encode meaningful temporal conditions and decidable (undecidability rules over interval temporal logics, while PNL is NEXPTIME-complete). Moreover, it is expressively complete with respect to the two-variable fragment of first-order logic extended with a linear order \(\text {FO} ^2[<]\). Various extensions of PNL have been studied in the literature, including metric, hybrid, and first-order ones. Here, we study the effects of the addition of an equivalence relation \(\sim \) to Metric PNL (MPNL\({\sim }\)). We first show that the finite satisfiability problem for PNL extended with \(\sim \) is still NEXPTIME-complete. Then, we prove that the same problem for MPNL\({\sim }\) can be reduced to the decidable 0–0 reachability problem for vector addition systems and vice versa (EXPSPACE-hardness immediately follows).