The complexity of temporal logic over the reals

DOI10.1016/j.apal.2010.01.002zbMath1235.03052OpenAlexW2031528374MaRDI QIDQ636345

M. A. Reynolds

Publication date: 26 August 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2010.01.002

zbMATH Keywords

temporal logicdecision problemPSPACE-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Related Items (13)

Metric temporal logic revisited ⋮ Metric temporal reasoning with less than two clocks ⋮ Time-Bounded Verification ⋮ Quantitative temporal logics over the reals: PSpace and below ⋮ Bounded variability of metric temporal logic ⋮ A survey on temporal logics for specifying and verifying real-time systems ⋮ The complexity of the temporal logic with ``until over general linear time ⋮ Temporal logics over linear time domains are in PSPACE ⋮ On the mosaic method for many-dimensional modal logics: a case study combining tense and modal operators ⋮ Timer formulas and decidable metric temporal logic ⋮ Unnamed Item ⋮ Complexity of monodic guarded fragments over linear and real time ⋮ Synthesis for continuous time

Cites Work

• Real-time logics: Complexity and expressiveness
• The decision problem for linear temporal logic
• An axiomatization for until and since over the reals without the IRR rule
• Reasoning in a restricted temporal logic
• The complexity of the temporal logic with ``until over general linear time
• Timer formulas and decidable metric temporal logic
• Relationships between nondeterministic and deterministic tape complexities
• Complexity of monodic guarded fragments over linear and real time
• The complexity of propositional linear temporal logics
• On the decidability of continuous time specification formalisms
• A propositional modal logic of time intervals
• An Axiomatization of the Temporal Logic with Until and Since over the Real Numbers
• On the elementary theory of linear order
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of temporal logic over the reals