#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (https://www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (https://homepage.mi-ras.ru/~sk/) и С.О. Сперанского (https://homepage.mi-ras.ru/~speranski/)

❗Замена

Доклад А.В. Грефенштейна откладывается в связи с болезнью. Вместо этого будет доклад С.О. Сперанского — см. подробности ниже.

Время: 4 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

С.О. Сперанский (МИАН)

О сложности первопорядковой логики вероятности с распределением на носителе

Первопорядковая логика вероятности с распределением на носителе — известный формальный язык для рассуждения о вероятностях в теоретической информатике, предложенный Дж. Хальперном. В односортной версии этой логики имеются кванторы по элементам носителя, а в двухсортной добавляются кванторы по вещественным числам.

Сложность вышеупомянутой логики была изучена М. Абади и Дж. Хальперном (1994). Основной интерес здесь представляют нижние сложностные оценки. Для их получения в статье М. Абади и Дж. Хальперна существенно использовались сложение и умножение между вероятностями. В настоящем докладе будет показано, как получить те же самые сложностные оценки для малых «качественных» (англ. qualitative) фрагментов, в которых нет ни сложения, ни умножения. В частности, в односортном случае будет достаточно равенств между вероятностями от бескванторных первопорядковых формул.

🔗 Семинар С. Л. Кузнецова и С. О. Сперанского "Вероятностные и субструктурные логические системы&


➰ ВК