Монадическая логика второго порядка
- Монадическая логика второго порядка (MSO) является фрагментом логики второго порядка с ограниченной количественной оценкой по множествам.
- MSO имеет фундаментальное значение в логике графов и теории автоматов.
- Логика второго порядка допускает количественную оценку с помощью предикатов, но MSO ограничена монадическими предикатами.
- Существуют два варианта монадической логики второго порядка: с немонадическими предикатами и только монадическими предикатами, за исключением равенства и упорядочивания.
- Экзистенциальная монадическая логика второго порядка (EMSO) ограничивает кванторы над множествами.
- Ограничение на монадическую логику позволяет доказать разделения, которые остаются недоказанными для немонадической логики второго порядка.
- Проверка графа на несвязность относится к монадическому NP, а проверка графа на связность не принадлежит к монадическому NP.
- Проблема выполнимости для монадической логики второго порядка неразрешима, но некоторые теории, такие как монадическая теория деревьев второго порядка, разрешимы.
- Монадическая логика деревьев второго порядка находит применение в формальной верификации для доказательства свойств программ и анализа аппаратного обеспечения.
Полный текст статьи: