Computational Complexity of a Hybridized Horn Fragment of Halpern-Shoham Logic

详细信息    查看全文

• 关键词：Interval logic ; Hybrid logic ; Computational complexity
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10119
• 期：1
• 页码：224-238
• 丛书名：Logic and Its Applications
• ISBN：978-3-662-54069-5
• 卷排序：10119

文摘

We propose hybridization of sub-propositional fragments of Halpern-Shoham logic as a way of obtaining expressive and decidable referential interval temporal logics. In the paper, we hybridize a Horn fragment of Halpern-Shoham logic whose language is restricted in its modal part to necessity modalities, and prove that satisfiability problem in this fragment is \(\textsc {NP}\)-complete over reflexive or an irreflexive and dense underlying structure of time.