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

M. Reynolds

doi:10.1016/S0022-0000(03)00005-9

Back

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

Journal article

Peer reviewed

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

M. Reynolds

Journal of Computer and System Sciences, Vol.66(2), pp.393-426

2003

DOI: https://doi.org/10.1016/S0022-0000(03)00005-9

Files and links (1)

url

Free to Read *No subscription requiredView

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.

Details

Title: The complexity of the temporal logic with “until” over general linear time
Authors/Creators: M. Reynolds (Author/Creator) - Murdoch University
Publication Details: Journal of Computer and System Sciences, Vol.66(2), pp.393-426
Publisher: Elsevier Science
Identifiers: 991005542350407891
Murdoch Affiliation: School of Information Technology
Language: English
Resource Type: Journal article

Metrics

48 Record Views

25 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.47 Software Engineering; 4.47.408 Model Checking
Web Of Science research areas: Computer Science, Hardware & Architecture; Computer Science, Theory & Methods
ESI research areas: Computer Science