Доповідь «Складність фрагментів логіки першого порядку з двома змінними»
У понеділок 24 жовтня 2016 року на кафедрі теорії та технології програмування факультету кібернетики Київського національного університету імені Тараса Шевченка відбудеться
доповідь
Єгора Гуськова
(аспірант Манчестерського університету)
з логіки розв’язання на тему
Єгора Гуськова
(аспірант Манчестерського університету)
з логіки розв’язання на тему
«Складність фрагментів логіки першого порядку з двома змінними»
Доповідь заснована на матеріалі дисертації, поданої на захист у Манчестерському університеті.
Початок — у 14:15.
Місце проведення: пр-т Академіка Глушкова 2, корпус 6 (станція метро "Виставковий центр"), ауд. уточнюється (для довідок і на початок підходьте на кафедру в ауд. 602).
Резюме доповіді:
Проблема розв’язання щодо істинності є нерозв’язною для логіки першого порядку. Натомість, ця проблема є експоненційно-повною в недетермінованому часі для логіки першого порядку з лише двома змінними. В той же час багато властивостей предикатів (наприклад, транзитивність) неможливо сформулювати у логіці першого
порядку за допомогою лише двох змінних.
Якщо заздалегідь вимагати спеціальних властивостей від окремого фіксованого предиката у формулах логіки першого порядку з двома змінними, то можна отримати логіку з більш широкими виражальними можливостями, ніж у звичайній логіці з двома змінними. В доповіді надається огляд таких розширень логіки першого порядку з двома змінними та їхніх класів складності, відомих на сьогоднішній день.
- Версія для друку
- Увійдіть щоб залишати відгуки
Останні коментарі
6 years 1 week тому
10 years 2 weeks тому
11 years 37 weeks тому
11 years 40 weeks тому
11 years 46 weeks тому
12 years 4 weeks тому
12 years 4 weeks тому
12 years 4 weeks тому
12 years 12 weeks тому
12 years 12 weeks тому