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.
翻译:在本文中,我们调查了依赖逻辑模型检查的参数复杂性,这是Team语义学领域一个研究周全的逻辑。我们首先列出了这一问题的九个直接参数,即:脱钩(即分裂)/(自由)变量/通用量化符、公式大小、盖夫曼图中输入结构、宇宙/团队大小和依赖原子的均匀性的树边宽。我们全面展示了模型检查的参数复杂性,并将问题分为可伸缩和各种难解度。此外,我们还通过确定输入部分来考虑模型检查问题的最重要变量(数据和表达复杂性)的复杂性。