1 citations · 1 across the 1 of their papers we have counts for
3 papers
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…
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…
Isomorphic Implication
Michael Bauland, Edith Hemaspaandra
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…