Intuitionistic modal logics: efficient fragments and parameterized complexity

ABSTRACT. A basic problem of logical inference systems is that of derivability: given a set of formulas X and a formula alpha, can alpha be derived from X using the inference rules? When the logical language is designed to express computational properties, the complexity of derivability assumes importance, and for most reasoning systems of even the propositional kind, the problem is hard. It is in this context that parameterized complexity offers hope for coping with hardness.