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.
*No subscription required
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|
|Copyright:||© 2003 Elsevier Science|
|Item Control Page|