Dependency quantified Boolean formulas (DQBF) extend quantified Boolean formulas with Henkin-style partially ordered quantifiers. It has been shown that this is likely to yield more succinct representations at the price of a computational blow-up from PSPACE to NEXPTIME. In this paper, we consider dependency quantified Horn formulas (DQHORN), a subclass of DQBF, and show that the computational simplicity of quantified Horn formulas is preserved when adding partially ordered quantifiers. We investigate the structure of satisfiability models for DQHORN formulas and prove that for both DQHORN and ordinary QHORN formulas, the behavior of the existential quantifiers depends only on the cases where at most one of the universally quantified variables is zero. This allows us to transform DQHORN formulas with free variables into equivalent QHORN formulas with only a quadratic increase in length. An application of these findings is to determine the satisfiability of a dependency quantified Horn formula Φ with ∣any∣ universal quantifiers in time O(∣any∣ · ∣Φ∣), which is just as hard as QHORN-SAT.
展开▼
机译：依赖性量化布尔公式（DQBF）与Henkin式部分有序量词延伸量化的布尔公式。已经表明，这可能会在从PSPACE到内西塞的计算爆炸价格上产生更简洁的表示。在本文中，我们考虑依赖性量化的喇叭公式（DQHORN），DQBF的子类，并且显示在添加部分有序的量子时保留量化的喇叭公式的计算简单性。我们调查DQHORN公式的可满足性模型的结构，并证明对于DQHORN和普通QHORN公式，存在量子量子的行为仅取决于大多数普遍定量变量为零的情况。这使我们能够将DQHORN公式与游离变量转换成等效QHORN公式，只有二次增加的长度。这些发现的应用是确定依赖性量化的喇叭公式φ的可满足性 - 时间o（| ANY |·|φB），这与Qhorn-SAT一样难以如此难。
展开▼
