Adding one or more equivalence relations to the interval temporal logic AB(B)over-bar

作者：Montanari Angelo^*; Pazzaglia Marco; Sala Pietro

来源：Theoretical Computer Science, 2016, 629: 116-134.

DOI：10.1016/j.tcs.2015.11.030

• Interval temporal logic
• Equivalence relation
• Decidability

Interval temporal logics provide a general framework for temporal representation and reasoning, where classical (point-based) linear temporal logics can be recovered as special cases. In this paper, we study the effects of the addition of one or more equivalence relations to one of the most representative interval temporal logics, namely, the logic AB (B) over bar of Allen's relations meets, begun by, and begins. We first prove that the satisfiability problem for the extension of AB (B) over bar with one equivalence relation remains decidable over finite linear orders, but it becomes nonprimitive recursive. Then, we show that decidability is lost over N. Finally, we show that the addition of two or more equivalence relations makes finite satisfiability for the resulting logic undecidable.

• 出版日期2016-5-23