Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Четверг, 17 октября 2019, 18:10–19:45
Где: НГУ, ауд. 4117

Описание

Однопроходные ветвящиеся программы как система доказательств. Эквивалентность регулярных резолюций и однопроходных ветвящихся программ. Эквивалентность разрешающих деревьев и древовидных резолюций.

Ширина резолюционных доказательств. Цейтинские формулы и их свойства, нижняя оценка на ширину через расширительную способность (e(G)).

Видео

Материалы

Текущая версия конспекта тут: https://logic.pdmi.ras.ru/~dmitrits/nsu/pc.pdf