Adding one or more equivalence relations to the interval temporal logic ABB¯

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 ABB¯ of Allen's relations meets, begun by, and begins  . We first prove that the satisfiability problem for the extension of ABB¯ with one equivalence relation remains decidable over finite linear orders, but it becomes nonprimitive recursive. Then, we show that decidability is lost over NN. Finally, we show that the addition of two or more equivalence relations makes finite satisfiability for the resulting logic undecidable.1