The complexity of propositional linear temporal logics

19851,099 citationsJournal Articlebronze Open Access

Authors

A. Prasad Sistla · University of Massachusetts Amherst

E. M. Clarke · Carnegie Mellon University

Abstract

The complexity of satisfiability and determination of truth in a particular finite structure are considered for different propositional linear temporal logics. It is shown that these problems are NP-complete for the logic with F and are PSPACE-complete for the logics with F, X, with U, with U, S, X operators and for the extended logic with regular operators given by Wolper.

Topics & Keywords

Logic, Reasoning, and Knowledge Advanced Algebra and Logic Logic, programming, and type systems

UN Sustainable Development Goals

Reduced inequalities

Publication Details

Published in: Journal of the ACM

Volume 32, Issue 3, pp. 733-749

DOI: 10.1145/3828.3837

Field-Weighted Citation Impact: 16.98