3 papers
cs.LO2008
The Complexity of Generalized Satisfiability for Linear Temporal Logic
Michael Bauland, Thomas Schneider, Henning Schnoor +2
In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of tempora…
cs.LO2008
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments
Michael Bauland, Martin Mundhenk, Thomas Schneider +3
In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the se…
cs.CC2008
Generalized Modal Satisfiability
Edith Hemaspaandra, Henning Schnoor, Ilka Schnoor
It is well known that modal satisfiability is PSPACE-complete (Ladner 1977). However, the complexity may decrease if we restrict the set of propositional operators used. Note that…