RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
9 апреля 2013 г. 18:30, г. Москва, ГЗ МГУ, ауд. 16-04
 


Об алгоритмической сложности замкнутого фрагмента логики доказуемости GLP

Ф. Н. Пахомов

Количество просмотров:
Эта страница:57

Аннотация: В докладе будут рассмотрены задачи распознавания выводимости в полимодальной логике доказуемости GLP для некоторых классов формул. Основным результатом является доказательство PSPACE-полноты указанной задачи для формул без пропозициональных переменных. Также установлено, что при каждом фиксированном $n$ задача рассматриваемого вида для формул без пропозициональных переменных, содержащих не более, чем $n$ различных модальных связок, решается за полиномиальное время.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017