RUS  ENG
Полная версия
СЕМИНАРЫ

Семинар С. Л. Кузнецова и С. О. Сперанского "Неклассические логики"
7 декабря 2022 г. 18:00, г. Москва, МИАН, комн. 313 (ул. Губкина, 8) + online


Семинар 12. Монадическая логика второго порядка. Теорема Бюхи–Элгота–Трахтенброта

Павел Соколов



Аннотация: В данном докладе мы рассмотрим монадический фрагмент логики второго порядка (MSO), то есть такой фрагмент, в котором кроме квантификации по элементам носителя разрешается квантификация только по одноместным предикатам (или, что эквивалентно, по подмножествам носителя). В частности, мы узнаем, что задачи выполнимости формул для некоторых теорий, выразимых в MSO, эквивалентны задачам о непустоте языков, распознаваемых некоторыми классами конечных автоматов (и, следовательно, достаточно эффективно решаются алгоритмически).


© МИАН, 2024