Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals |
| |
Institution: | 1. Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland;2. Institut für Theoretische Informatik, Leibniz Universität Hannover, Hannover, Germany;3. Department of Computer Science, University of Sheffield, Sheffield, United Kingdom |
| |
Abstract: | 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. |
| |
Keywords: | Dependence logic Team semantics Metafinite structures Blum-Shub-Smale machine |
本文献已被 ScienceDirect 等数据库收录! |
|