The complexity of temporal logic over the reals

Annals of Pure and Applied Logic 161 (8):1063-1096 (2010)
  Copy   BIBTEX

Abstract

It is shown that the decision problem for the temporal logic with until and since connectives over real-numbers time is PSPACE-complete. This is the most practically useful dense time temporal logic

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2010.01.002

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,440

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Recursive Approximability of Real Numbers.Xizhong Zheng - 2002 - Mathematical Logic Quarterly 48 (S1):131-156.
Logics which capture complexity classes over the reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
Algorithmic randomness and measures of complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Cohen reals from small forcings.Janusz Pawlikowski - 2001 - Journal of Symbolic Logic 66 (1):318-324.
Schnorr trivial reals: a construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Mapping a set of reals onto the reals.Arnold W. Miller - 1983 - Journal of Symbolic Logic 48 (3):575-584.
Regular reals.Guohua Wu - 2005 - Mathematical Logic Quarterly 51 (2):111-119.
An axiomatization for until and since over the reals without the IRR rule.Mark Reynolds - 1992 - Studia Logica 51 (2):165 - 193.
From a well-ordering of the reals it is easy (by a diagonal argument) to produce a non-determined set of reals. However, large cardinal axioms imply that all sets of reals in L (R), and more, are determined. See, for example, Neeman's papers Optimalproofs of determinacy.Andrzej S. Murawski - 1995 - Bulletin of Symbolic Logic 1:327-339.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Exact equiconsistency results for Δ 3 1 -sets of reals.Haim Judah - 1992 - Archive for Mathematical Logic 32 (2):101-112.
Adding a temporal dimension to a logic system.Marcelo Finger & Dov M. Gabbay - 1992 - Journal of Logic, Language and Information 1 (3):203-233.

Analytics

Added to PP
2013-12-18

Downloads
68 (#241,796)

6 months
8 (#373,029)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Temporal logic.Antony Galton - 2008 - Stanford Encyclopedia of Philosophy.
A Tableau for Temporal Logic over the Reals.Mark Reynolds - 2014 - In Rajeev Goré, Barteld Kooi & Agi Kurucz (eds.), Advances in Modal Logic, Volume 10. CSLI Publications. pp. 439-458.
Temporal logic.Temporal Logic - forthcoming - Stanford Encyclopedia of Philosophy.
Synthesis for Temporal Logic over the Reals.Tim French, John McCabe-Dansted & Mark Reynolds - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 217-238.

View all 7 citations / Add more citations

References found in this work

The decision problem for linear temporal logic.John P. Burgess & Yuri Gurevich - 1985 - Notre Dame Journal of Formal Logic 26 (2):115-128.
Complexity of monodic guarded fragments over linear and real time.Ian Hodkinson - 2006 - Annals of Pure and Applied Logic 138 (1):94-125.

Add more references