The complexity of the temporal logic with ``until over general linear time

DOI10.1016/S0022-0000(03)00005-9zbMath1019.03014MaRDI QIDQ1400578

M. A. Reynolds

Publication date: 13 August 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Related Items (11)

Metric temporal reasoning with less than two clocks ⋮ A survey on temporal logics for specifying and verifying real-time systems ⋮ Temporal logics over linear time domains are in PSPACE ⋮ Complexity of hybrid logics over transitive frames ⋮ On the mosaic method for many-dimensional modal logics: a case study combining tense and modal operators ⋮ The complexity of temporal logic over the reals ⋮ On the expressiveness of TPTL and MTL ⋮ Linear-time temporal logics with Presburger constraints: an overview ★ ⋮ REASONING ABOUT TRANSFINITE SEQUENCES ⋮ Complexity of monodic guarded fragments over linear and real time ⋮ Synthesis for continuous time

Cites Work

• The complexity of temporal logic over the reals
• The decision problem for linear temporal logic
• A decidable temporal logic of parallelism
• Axioms for tense logic. I: 'Since' and 'until'
• On the size of refutation Kripke models for some linear modal and tense logics
• An axiomatization for until and since over the reals without the IRR rule
• Reasoning in a restricted temporal logic
• Logic at work. Essays dedicated to the memory of Helena Rasiowa
• Relationships between nondeterministic and deterministic tape complexities
• The complexity of propositional linear temporal logics
• On the decidability of continuous time specification formalisms
• On the elementary theory of linear order
• Elementary properties of ordered abelian groups
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of the temporal logic with ``until over general linear time