Доповідь «Складність фрагментів логіки першого порядку з двома змінними»

У понеділок 24 жовтня 2016 року на кафедрі теорії та технології програмування факультету кібернетики Київського національного університету імені Тараса Шевченка відбудеться

Доповідь заснована на матеріалі дисертації, поданої на захист у Манчестерському університеті.

Початок — у 14:15.

Місце проведення: пр-т Академіка Глушкова 2, корпус 6 (станція метро "Виставковий центр"), ауд. уточнюється (для довідок і на початок підходьте на кафедру в ауд. 602).

Резюме доповіді:

Проблема розв’язання щодо істинності є нерозв’язною для логіки першого порядку. Натомість, ця проблема є експоненційно-повною в недетермінованому часі для логіки першого порядку з лише двома змінними. В той же час багато властивостей предикатів (наприклад, транзитивність) неможливо сформулювати у логіці першого
порядку за допомогою лише двох змінних.

Якщо заздалегідь вимагати спеціальних властивостей від окремого фіксованого предиката у формулах логіки першого порядку з двома змінними, то можна отримати логіку з більш широкими виражальними можливостями, ніж у звичайній логіці з двома змінними. В доповіді надається огляд таких розширень логіки першого порядку з двома змінними та їхніх класів складності, відомих на сьогоднішній день.