Other
papers online
The Complexity of Temporal Logic over the Reals
Mark
Reynolds
Abstract
It is shown that the decision problem for the temporal logic with until
and since connectives over real-numbers time is PSPACE-complete.
Full Paper
Official Annals of Pure and Applied Logic published online version:
doi:10.1016/j.apal.2010.01.002
Status
The original technical report appeared online in 1999
(see here)
but it took a long time to get submitted and
reviewed (as it is a long and technical
paper).
The latest version (2009)
has been
accepted for publication
in the Annals of Pure and Applied Logic
and is available online but not in
paper yet.
More details about publication information
will be posted here when they are available.
Note that some follow on results
on the complexity of other temporal logics
have been further developed in
a separate (draft) paper.
See
here.
Bibtex
@article{Rey:cort,
author="M. Reynolds",
title="The Complexity of the Temporal Logic over the Reals",
journal="Annals of Pure and Applied Logic",
year="accepted 2009",
note="in press, doi:10.1016/j.apal.2010.01.002"
}