Decomposing Modal Logic
Carlos Areces, Maarten de Rijke, Gabriel Infante-Lopez

Abstract:
We provide a detailed analysis of very weak fragments of modal
logic. Our fragments lack connectives that introduce non-determinism
and they feature restrictions on the modal operators, which may lead
to substantial reductions in complexity.  Our main result is a general
game-based characterization of the expressive power of our fragments
over the class of finite structures