Catalog Home Page

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

Reynolds, M. (2003) The complexity of the temporal logic with “until” over general linear time. Journal of Computer and System Sciences, 66 (2). pp. 393-426.

Free to read: http://dx.doi.org/10.1016/S0022-0000(03)00005-9
*No subscription required

Abstract

It is shown that the decision problem for the temporal logic with the strict until operator over general linear time is PSPACE-complete. This shows that it is no harder to reason with arbitrary linear orderings than with discrete linear time temporal logics. New techniques are used to give a PSPACE procedure for the logic.

Publication Type: Journal Article
Murdoch Affiliation: School of Information Technology
Publisher: Elsevier Science
Copyright: © 2003 Elsevier Science
URI: http://researchrepository.murdoch.edu.au/id/eprint/18481
Item Control Page Item Control Page