The complexity of propositional linear temporal logics
Authors:
- A. P. SistlaASA. P. Sistla
- E. M. ClarkeECE. M. Clarke
Open Access
- 5 May 1982
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 159-168
Abstract
We consider the complexity of satisfiability and determination of truth in a particular finite structure for different propositional linear temporal logics. We show that both the above problems are NP-complete for the logic with F operator and are PSPACE-complete for the logics with F,X, with U, with U,S,X, and Wolper's extended logic with regular operators [Wo81].Keywords
This publication has 4 references indexed in Scilit:
- The temporal logic of branching time1981
- On the temporal analysis of fairness1980
- Propositional dynamic logic of regular programsJournal of Computer and System Sciences, 1979
- The Computational Complexity of Provability in Systems of Modal Propositional LogicSIAM Journal on Computing, 1977