Computational complexity of hybrid interval temporal logics
type: Item
instance of: scholarly article
title: Computational complexity of hybrid interval temporal logics
author: Przemysław Andrzej Wałęga
published in: Annals of Pure and Applied Logic
publication date: 2022-10-14T00:00:00Z
review text: 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.
reviewed by: Giacomo Lenzi
Mathematics Subject Classification ID: 03B44
Mathematics Subject Classification ID: 03B70
Mathematics Subject Classification ID: 03B45
Mathematics Subject Classification ID: 68T27
zbMATH DE Number: 7601548
zbMATH Keywords: temporal logic
zbMATH Keywords: hybrid logic
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: j.apal.2022.103165
OpenAlex ID: W4285009574
cites work: A complete classification of the expressiveness of interval logics of Allen's relations: the general and the dense cases
cites work: Maintaining knowledge about temporal intervals
cites work: Towards a general theory of action and time
cites work: The computational complexity of hybrid temporal logics
cites work: Q4230717
cites work: Representation, reasoning, and relational structures: a hybrid logic manifesto
cites work: Arthur Prior and `now'
cites work: Hybrid languages and temporal logic
cites work: The complexity of temporal constraint satisfaction problems
cites work: Relational dual tableaux for interval temporal logics ★
cites work: The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT
cites work: Interval temporal logics over strongly discrete linear orders: expressiveness and complexity
cites work: Sub-propositional Fragments of the Interval Temporal Logic of Allen’s Relations
cites work: On the Complexity of Fragments of the Modal Logic of Allen’s Relations over Dense Structures
cites work: Horn Fragments of the Halpern-Shoham Interval Temporal Logic
cites work: Temporal constraint networks
cites work: Q4012170
cites work: Modal logic with names
cites work: A Road Map of Interval Temporal Logics and Duration Calculi
cites work: A general tableau method for propositional interval temporal logics: theory and implementation
cites work: A propositional modal logic of time intervals
cites work: The Undecidability of the Logic of Subintervals
cites work: Dual tableaux. Foundations, methodology, case studies
cites work: Expressiveness and completeness of an interval tense logic
cites work: A Modal Logic for Chopping Intervals
cites work: Computational Complexity of a Hybridized Horn Fragment of Halpern-Shoham Logic
cites work: Q5079792
cites work: Hybrid fragments of Halpern-Shoham logic and their expressive power
cites work: Computational complexity of core fragments of modal logics \(\mathrm{t}\), \(\mathrm{K4}\), and \(\mathrm{S4}\)
cites work: On expressiveness of Halpern-Shoham logic and its Horn fragments
DOI: 10.1016/J.APAL.2022.103165
description: scientific article; zbMATH DE number 7601548