93 citations · 122 across the 9 of their papers we have counts for
11 papers
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…
The Complexity of Plan Existence and Evaluation in Probabilistic Domains
Judy Goldsmith, Michael L. Littman, Martin Mundhenk
We examine the computational complexity of testing and finding small plans in probabilistic planning domains with succinct representations. We find that many problems of interest a…
The Complexity of Monotone Hybrid Logics over Linear Frames and the Natural Numbers
Stefan Göller, Arne Meier, Martin Mundhenk +3
Hybrid logic with binders is an expressive specification language. Its satisfiability problem is undecidable in general. If frames are restricted to N or general linear orders, the…
Intuitionistic implication makes model checking hard
Martin Mundhenk, Felix Weiss
We investigate the complexity of the model checking problem for intuitionistic and modal propositional logics over transitive Kripke models. More specific, we consider intuitionist…
Nonapproximability Results for Partially Observable Markov Decision Processes
J. Goldsmith, C. Lusena, M. Mundhenk
We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have…
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…