Эта публикация цитируется в
1 статье
О схлопывании вероятностных иерархий. I
С. О. Сперанский Новосибирский гос. ун-т, ул. Пирогова, 2, г. Новосибирск, 630090, РОССИЯ
Аннотация:
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой
$\mathcal{QPL}$, и её вариантов. Доказывается: если подполе
$\mathfrak F$ вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над
$\mathfrak F$-значными вероятностными структурами для
$\Sigma_4$-
$\mathcal{QPL}$-предложений является
$\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при доказательстве этого факта устанавливается
$\Pi^1_1$-полнота
$\forall\exists$-теории арифиметики Пресбургера с единственным свободным одноместным предикатом, что обобщает известный результат Хальперна, относящийся ко всей упомянутой теории.
Ключевые слова:
вероятностная логика, кванторы по пропозициям, вычислительная сложность, выразительность.
УДК:
510.647+
510.5 Поступило: 01.08.2012
Окончательный вариант: 05.03.2013