|
This article is cited in 1 scientific paper (total in 1 paper)
Collapsing probabilistic hierarchies. I
S. O. Speranskii Novosibirsk State University, Novosibirsk, Russia
Abstract:
We study hierarchies of validity problems for prefix fragments in probability logic with quantifiers over propositional formulas, denoted $\mathcal{QPL}$, and its versions. It is proved that if a subfield $\mathfrak F$ of reals is definable in the standard model of arithmetic by a second-order formula without set quantifiers, then the validity problem over $\mathfrak F$-valued probability structures for $\Sigma_4$-$\mathcal{QPL}$-sentences is $\Pi^1_1$-complete; as a consequence, the corresponding hierarchy of validity problems collapses. Moreover, in proving this fact, we state that an $\Pi^1_1$-полнота $\forall\exists$-theory of Presburger arithmetic with a single free unary predicate is $\Pi^1_1$-complete, which generalizes a well-known result of Halpern relating to the entire theory mentioned.
Keywords:
probability logic, quantifiers over propositions, computational complexity, expressiveness.
Received: 01.08.2012 Revised: 05.03.2013
Citation:
S. O. Speranskii, “Collapsing probabilistic hierarchies. I”, Algebra Logika, 52:2 (2013), 236–254; Algebra and Logic, 52:2 (2013), 159–171
Linking options:
https://www.mathnet.ru/eng/al584 https://www.mathnet.ru/eng/al/v52/i2/p236
|
Statistics & downloads: |
Abstract page: | 325 | Full-text PDF : | 78 | References: | 64 | First page: | 37 |
|