
arXiv: 2306.00420
handle: 10138/595455 , 10138/586131
Abstract We study the expressivity and the complexity of various logics in probabilistic team semantics with the Boolean negation. In particular, we study the extension of probabilistic independence logic with the Boolean negation, and a recently introduced logic first-order theory of random variables with probabilistic independence. We give several results that compare the expressivity of these logics with the most studied logics in probabilistic team semantics setting, as well as relating their expressivity to a numerical variant of second-order logic. In addition, we introduce novel entropy atoms and show that the extension of first-order logic by entropy atoms subsumes probabilistic independence logic. Finally, we obtain some results on the complexity of model checking, validity and satisfiability of our logics.
FOS: Computer and information sciences, Model checking, Computer Science - Logic in Computer Science, Computational Complexity, Computer and information sciences, Computational Complexity (cs.CC), Probabilistic team semantics, Model Checking, Validity, Logic in Computer Science (cs.LO), Computational complexity, Computer Science - Computational Complexity, Expressivity of Logics, Probabilistic Team Semantics, Satisfiability, Expressivity of logics, Mathematics
FOS: Computer and information sciences, Model checking, Computer Science - Logic in Computer Science, Computational Complexity, Computer and information sciences, Computational Complexity (cs.CC), Probabilistic team semantics, Model Checking, Validity, Logic in Computer Science (cs.LO), Computational complexity, Computer Science - Computational Complexity, Expressivity of Logics, Probabilistic Team Semantics, Satisfiability, Expressivity of logics, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
