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

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




Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
16 декабря 2019 г. 18:30, г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Zoom
 


Decidable and undecidable problems for modal definability and first-order definability

Philippe Balbiani

Univ. Toulouse
Видеозаписи:
MP4 2,764.5 Mb
MP4 1,796.0 Mb

Количество просмотров:
Эта страница:309
Видеофайлы:79
Youtube:

Philippe Balbiani



Аннотация: The core of our talk will be Chagrova's Theorem about modal definability of given elementary conditions. Its proof is based on the undecidability of a variant of the halting problem concerning Minsky machines. It cannot be easily repeated for showing that, with respect to different classes of frames, the problem of deciding the modal definability of given elementary conditions is undecidable too. We will give a new proof of Chagrova's Theorem. We will also give the proofs of new variants of Chagrova's Theorem. In particular, we will study modal correspondence theory in the class of all Euclidean frames by showing that with respect to this class of frames, every modal formula is first-order definable and the problem of deciding the modal definability of given elementary conditions is undecidable. Finally, we will study modal correspondence theory in the class of all partitions by showing that with respect to this class of frames, every modal formula is first-order definable and the problem of deciding the modal definability of given elementary conditions is PSPACE-complete.

Язык доклада: английский
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024