The complexity of propositional linear temporal logics
- 1 January 1982
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 159-168
- https://doi.org/10.1145/800070.802189
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 0 references indexed in Scilit: