The complexity of propositional linear temporal logics
- 1 July 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (3), 733-749
- https://doi.org/10.1145/3828.3837
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.Keywords
This publication has 3 references indexed in Scilit:
- On the size of refutation Kripke models for some linear modal and tense logicsStudia Logica, 1980
- The Computational Complexity of Provability in Systems of Modal Propositional LogicSIAM Journal on Computing, 1977
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970