|
|
«Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна)
9 апреля 2013 г. 18:30–20:05, г. Москва, Математический институт им.В.А.Стеклова РАН
|
 |
|
 |
|
|
|
Об алгоритмической сложности замкнутого фрагмента логики доказуемости GLP
Ф. Н. Пахомов |
| Количество просмотров: |
| Эта страница: | 203 |
|
Аннотация:
В докладе будут рассмотрены задачи распознавания выводимости в полимодальной логике доказуемости GLP для некоторых классов формул. Основным результатом является доказательство PSPACE-полноты указанной задачи для формул без пропозициональных переменных. Также установлено, что при каждом фиксированном $n$ задача рассматриваемого вида для формул без пропозициональных переменных, содержащих не более, чем $n$ различных модальных связок, решается за полиномиальное время.
|
|
Обратная связь: