93 citations · 122 across the 9 of their papers we have counts for
5 papers · 1 filter
The model checking fingerprints of CTL operators
Andreas Krebs, Arne Meier, Martin Mundhenk
The aim of this study is to understand the inherent expressive power of CTL operators. We investigate the complexity of model checking for all CTL fragments with one CTL operator a…
Model Checking CTL is Almost Always Inherently Sequential
Olaf Beyersdorff, Arne Meier, Martin Mundhenk +3
The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the…
The Complexity of Satisfiability for Fragments of Hybrid Logic -- Part I
Arne Meier, Martin Mundhenk, Thomas Schneider +3
The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this pa…
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…