The complexity of propositional linear temporal logics

Authors:
  • ASA. P. Sistla
    A. P. Sistla
  • ECE. M. Clarke
    E. M. Clarke

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].

This publication has 4 references indexed in Scilit: