Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




Seminars "Proof Theory" and "Logic Online Seminar"
December 16, 2019 18:30, Moscow, Steklov Mathematical Institute (8 Gubkina), room 313 + Zoom
 


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

Philippe Balbiani

Univ. Toulouse
Video records:
MP4 2,764.5 Mb
MP4 1,796.0 Mb

Number of views:
This page:282
Video files:77
Youtube:

Philippe Balbiani



Abstract: 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.

Language: English
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024