  In this paper, we investigate the parameterized complexity of model checking
for Dependence Logic which is a well studied logic in the area of Team
Semantics. We start with a list of nine immediate parameterizations for this
problem, namely: the number of disjunctions (i.e., splits)/(free)
variables/universal quantifiers, formula-size, the tree-width of the Gaifman
graph of the input structure, the size of the universe/team, and the arity of
dependence atoms. We present a comprehensive picture of the parameterized
complexity of model checking and obtain a division of the problem into
tractable and various intractable degrees. Furthermore, we also consider the
complexity of the most important variants (data and expression complexity) of
the model checking problem by fixing parts of the input.

Logic in Computer Science