Geodesic
Collapsing probabilistic hierarchies.~I
Algebra i logika, Tome 52 (2013) no. 2, pp. 236-254.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, computational complexity, expressiveness.
Mots-clés : quantifiers over propositions 
@article{AL_2013_52_2_a6,
     author = {S. O. Speranskii},
     title = {Collapsing probabilistic {hierarchies.~I}},
     journal = {Algebra i logika},
     pages = {236--254},
     publisher = {mathdoc},
     volume = {52},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2013_52_2_a6/}
}
TY  - JOUR
AU  - S. O. Speranskii
TI  - Collapsing probabilistic hierarchies.~I
JO  - Algebra i logika
PY  - 2013
SP  - 236
EP  - 254
VL  - 52
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2013_52_2_a6/
LA  - ru
ID  - AL_2013_52_2_a6
ER  - 
%0 Journal Article
%A S. O. Speranskii
%T Collapsing probabilistic hierarchies.~I
%J Algebra i logika
%D 2013
%P 236-254
%V 52
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2013_52_2_a6/
%G ru
%F AL_2013_52_2_a6
S. O. Speranskii. Collapsing probabilistic hierarchies.~I. Algebra i logika, Tome 52 (2013) no. 2, pp. 236-254. http://geodesic.mathdoc.fr/item/AL_2013_52_2_a6/

[1] J. Y. Halpern, “Presburger arithmetic with unary predicates is $\Pi^1_1$ complete”, J. Symb. Log., 56:2 (1991), 637–642 | DOI | MR | Zbl

[2] M. Abadi, J. Y. Halpern, “Decidability and expressiveness for first-order logics of probability”, Inf. Comput., 112:1 (1994), 1–36 | DOI | MR | Zbl

[3] S. O. Speranski, “Complexity for probability logic with quantifiers over propositions”, J. Log. Comput., 2012 | DOI | Zbl

[4] R. Fagin, J. Y. Halpern, N. Megiddo, “A logic for reasoning about probabilities”, Inf. Comput., 87:1–2 (1990), 78–128 | DOI | MR | Zbl

[5] S. O. Speranskii, “Kvantifikatsiya po propozitsionalnym formulam v veroyatnostnoi logike: voprosy razreshimosti”, Algebra i logika, 50:4 (2011), 533–546 | MR | Zbl

[6] J. Y. Halpern, “An analysis of first-order logics of probability”, Artif. Intell., 46:3 (1990), 311–350 | DOI | MR | Zbl

[7] D. Harel, A. Pnueli, J. Stavi, “Propositional dynamic logic of nonregular programs”, J. Comput. Syst. Sci., 26:2 (1983), 222–243 | DOI | MR | Zbl

[8] C. Smorynski, Self-Reference and modal logic, Universitext, Springer-Verlag, New York etc., 1985 | DOI | MR

[9] S. G. Simpson, Subsystems of second order arithmetic, Perspect. Logic, 2nd ed., Cambrige Univ. Press, Cambridge; Assoc. Symb. Log., Urbana, IL, 2009 | MR | Zbl