Computational complexity of hybrid interval temporal logics (Q2084954)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computational complexity of hybrid interval temporal logics |
scientific article |
Statements
Computational complexity of hybrid interval temporal logics (English)
0 references
14 October 2022
0 references
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.
0 references
temporal logic
0 references
hybrid logic
0 references
computational complexity
0 references
0 references
0 references
0 references