93 citations · 122 across the 9 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
cs.CC2011★ 2 cited
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…
cs.AI2011★ 93 cited
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…
cs.LO2011★ 9 cited
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…