The Complexity of Generalized Satisfiability for Linear Temporal Logic (2008)
Bauland, Michael, Schneider, Thomas, Schnoor, Henning, Schnoor, Ilka, Vollmer, Heribert
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 temporal operators used....
Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor D
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 set of temporal...
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments (2008)
Bauland, Michael, Mundhenk, Martin, Schneider, Thomas, Schnoor, Henning, Schnoor, Ilka, Vollmer, Heribert
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 set of temporal...
Bauland, Michael, Hemaspaandra, Edith
We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints,...