  The methods used to establish PSPACE-bounds for modal logics can roughly be
grouped into two classes: syntax driven methods establish that exhaustive proof
search can be performed in polynomial space whereas semantic approaches
directly construct shallow models. In this paper, we follow the latter approach
and establish generic PSPACE-bounds for a large and heterogeneous class of
modal logics in a coalgebraic framework. In particular, no complete
axiomatisation of the logic under scrutiny is needed. This does not only
complement our earlier, syntactic, approach conceptually, but also covers a
wide variety of new examples which are difficult to harness by purely syntactic
means. Apart from re-proving known complexity bounds for a large variety of
structurally different logics, we apply our method to obtain previously unknown
PSPACE-bounds for Elgesem's logic of agency and for graded modal logic over
reflexive frames.

Logic in Computer Science;Artificial Intelligence;Computational Complexity;Multiagent Systems