32 citations · 72 across the 9 of their papers we have counts for
3 papers · 2 filters
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…
Complexity of Hybrid Logics over Transitive Frames
Martin Mundhenk, Thomas Schneider, Thomas Schwentick +1
This paper examines the complexity of hybrid logics over transitive frames, transitive trees, and linear frames. We show that satisfiability over transitive frames for the hybrid l…
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…