Complexity Results for Modal Dependence Logic
Complexity Results for Modal Dependence Logic
复制标题
模态依赖逻辑的复杂性结果
DOI：
10.1007/s11225-013-9483-6
复制
发表时间：
2013
期刊：
影响因子：
0.7
通讯作者：
H. Vollmer
中科院分区：
文献类型：
--
作者：
P. Lohmann;H. Vollmer
模态依赖逻辑最近由Väänänen引入。它通过操作符=（）增强了基本模态语言。对于命题变量p1，. . .，pn，=（p1，. . .，pn-1，pn）直观地表明，由p1，. . .，pn-1。Sevenster（J. Logic and Computation，2009）证明了模态依赖逻辑的可满足性对于非确定性指数时间是完全的，本文考虑通过限制允许命题连接词的集合得到的模态依赖逻辑的片段。我们证明了穷人依赖逻辑的可满足性，这种语言由文字和依赖原子使用（i）建立的公式组成。例如，不允许分离），保持NEXPTIME-完成。如果我们只允许单调公式（没有否定，但有析取），复杂性下降到PSPACE-完全。我们还扩展了Väänänen的语言，除了依赖析取之外还允许经典析取，并证明可满足性问题仍然是NEXPTIME-完全的。如果我们不允许否定和依赖析取，则多项式层次的第二层的可满足性是完全的。此外，我们考虑了模态依赖逻辑的限制，其中每个单个依赖原子的长度由整个逻辑固定的数字限制。我们证明了这个有界元依赖逻辑的可满足性问题是PSPACE-完全的，并且如果我们不允许析取，复杂性下降到多项式层次的第三级，这样我们就完全分类了Väänänen和Sevenster所考虑的命题和依赖算子的所有限制的可满足性问题的计算复杂性.
Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variablesp1, . . . ,pn, = (p1, . . . ,pn-1,pn) intuitively states that the value ofpnis determined by those ofp1, . . . ,pn-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic exponential time.In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability forpoor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using(i. e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness.We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACE-complete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster.
登录
查看更多内容
影响因子：
14.4
作者：
F. M. Donini;M. Lenzerini;D. Nardi;B. Hollunder;W. Nutt;A. Marchetti
通讯作者：
A. Marchetti
DOI：
10.1007/bf01744287
发表时间：
1979
期刊：
Mathematical systems theory
影响因子：
--
作者：
H. R. Lewis
通讯作者：
H. R. Lewis
模态依赖逻辑
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
J. Väänänen
通讯作者：
J. Väänänen
作为一种语义现象的信息独立性
DOI：
10.1016/s0049-237x(08)70066-1
发表时间：
1989
期刊：
Studies in logic and the foundations of mathematics
影响因子：
--
作者：
J. Hintikka;G. Sandu
通讯作者：
G. Sandu
布尔电路定义的问题的复杂性
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
S. Reith;K. Wagner;L. Theoretische
通讯作者：
L. Theoretische