论文标题
概率团队语义和真实的生存二阶逻辑中的障碍边界
Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
论文作者
论文摘要
概率团队语义是逻辑分析概率依赖性的框架。我们的重点是概率包含逻辑及其扩展的公理化，复杂性和表现力。我们将具有添加剂真实算术的生存二阶逻辑的自然片段确切捕获概率包含逻辑的表达性。我们将这些形式主义与线性编程联系起来，并为逻辑获得PTIME数据复杂性。此外，在有限结构上，我们表明具有添加性真实算术的完整二阶逻辑只能表达NP属性。最后，我们为原子水平上的概率包含逻辑提供了声音和完整的公理化。
Probabilistic team semantics is a framework for logical analysis of probabilistic dependencies. Our focus is on the axiomatizability, complexity, and expressivity of probabilistic inclusion logic and its extensions. We identify a natural fragment of existential second-order logic with additive real arithmetic that captures exactly the expressivity of probabilistic inclusion logic. We furthermore relate these formalisms to linear programming, and doing so obtain PTIME data complexity for the logics. Moreover, on finite structures, we show that the full existential second-order logic with additive real arithmetic can only express NP properties. Lastly, we present a sound and complete axiomatization for probabilistic inclusion logic at the atomic level.
