Computational complexity of hybrid interval temporal logics (Q2084954)

The paper studies interval temporal logic enriched with nominals. The focus is on computational complexity. Section 2 considers Halpern-Shoham interval temporal logic. In Section 3 nominals are introduced, which allow one to refer to specific intervals. In Section 4 and later it is demonstrated that adding nominals may increase computational complexity. For instance, several NP hardness results are proved for satisfiability problems, via reduction of the usual propositional satisfiability problem. In Section 5 we have several NP upper bounds for some logics, contrary to the feasibility in P of the version without nominals. In Section 6, using Turing machines, higher hardness results are proved, such as PSPACE-hardness and undecidability.