> Merkliste Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp: E-Artikel; Sonstige Veröffentlichung Titel: Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals Beteiligte: Hannula, Miika [VerfasserIn]; Virtema, Jonni [VerfasserIn] Erschienen: Amsterdam [u.a.] : Elsevier, 2022 Erschienen in: Annals of pure and applied logic 173 (2022), Nr. 10 ; Annals of pure and applied logic Ausgabe: published Version Sprache: Englisch DOI: https://doi.org/10.15488/12824; https://doi.org/10.1016/j.apal.2022.103108 Schlagwörter: Dependence logic ; Blum-Shub-Smale machine ; Metafinite structures ; Team semantics Entstehung: Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen. Beschreibung: 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. © 2022 The Author(s) Zugangsstatus: Freier Zugang Rechte-/Nutzungshinweise: Namensnennung (CC BY)